前言
今天公开元旦解题活动第一题答案,感谢大家的参与。
第一题 write up
提示已经给的很明显了,就是RSA算法
下面给出RSA基本原理
找出两个不同的素数p、q
n = p*q
根据欧拉函数,φ(n) = (p-1)*(q-1)
找到一个公钥e,使1<e<φ(n),同时e与φ互素
找到d使e*d/φ(n)的余数为1
公钥:(n,e)
私钥:(n,d)
首先去官网下载案例(搜一下就能知道官网):
https://www.jansh.com.cn/download/file_download.php?id=47
在这个案例里面有个文件:test.cpp
根据这个文件,我们可以解析公钥,然后根据这个结构去解析私钥即可。
先看看案例中的公钥结构
根据注释信息可以知道,开头的00 00 01 00为长度信息,提示后面要读取的长度,且为n的值,那么这里就是0100=>256,需要读取256字节长度。
上图就是n的值,然后继续读取长度信息,00 00 00 04这个就是后面要读取的长度信息,04=>4,需要读取4个字节,即00 01 00 01,其实熟悉RSA的朋友已经看出来这是什么了,这就是e的值,且为65537。
根据示例可以知道,解析这个文件需要每次先读取4字节的长度信息,然后根据长度读取需要的内容,有了这个基本原理,我们就可以解析私钥了,下面尝试解析示例中的私钥。
这里的前四个字节明显不对,我们尝试读取两个字节,即01 00和00 80,那么80=>128,后面读取128字节的信息,以此类推会获得下面几个值:
FB0BAD128CC8E130A7BF98D83B9DEC28B4A919CA530B29D9C3D642C2B92502610B445871D0D190B8B1508733D928F96DD3894EBC3E6289ECBEDEBAC009D780567C292AAC05486E0BBE481D73A271203E882A135D08214838FE508BF35F5C00A17155535B1AFA41959299A006A531917B74F6A86DD735696228EE47CA89BE9137
D304628A2429B7B3A701B6BE76F2434D9EAB5DDABD44D1AFCD6E49AC1227C8D0A62861F0DF134B7DCBC543A6BEFACDA589A0084DF2655CE4930BA73D7CB523934E4A4C35512508B831D62E67CD3A2450CA2402E67DB030D87CDE4F6A8F9A44C5617337311FAB13EB4CD610F853924AB9B44275AC7447E02D005B4FDB26455FD3
449A23387F7A61773F4FEF3F9FC2FF06FC9F7D29B9D9C21CFD142EF83149F8C57623BE1B9419C0778814DE6D7FB95FB7F067843992BEB0BC1E489535E73A999A88A16344D0C8C331B854D29F87D36C214A6A5D123E278229F8ED1FE168BCA67B7791FE8E55E7EF4625628FC5611D13896E23FD50CECF8CB5C343A220A9D586AF
719EF2D01F18B7696C8B67B2B6A94BC407A38E2DB1ABD49C2CA92DD211148AF48E0340794A244189C2A6BCFE93E6C7C4528E70EA47927CAA36E31771EC2C3CB39C7C34FCA06CA87D459865F44E74F808E84EEBA0E01C76B09ACBB9474F7B697C3E34A38B37DA0E27AC7FB7337F0C4E601FC789450A778925B20378C42F9F3B31
8568AFFBA18833933CF3E26933D66F84042495EF309B23124001993F27645F603961E4982E2EC54B13B1F37E64B6F9CD32488E78A2147965B347EB3B89CFB833E89129588693B4996E0A71C7EFF9CEF56E2B67679ACBBE02566698E70BDC574F92E6CD3513CA7E42FB5866C627FAE204D48CB66111E2BDC3A27041AA7DDD7F76
这里明显有个问题,出现了5个数字,而且长度都是128字节,那么可以断定里面不存在n、e和d,当然不存在Dq、Dp只有可能p、q。
为什么?因为n、e组成公钥,n为p*q,这里都是128字节,明显不够。e没有这么长,况且前面已经得到了,正常来说私钥只有d和n,这里5个值都不等于n也不够,是不是d也不好确定,我这里采用最简单的办法,认为私钥存储了p、q,我们只需要用这5个数交叉生成密钥,然后使用案例的公钥加密一段文字,然后我们解密就知道了。
说真的,我只用了一次就成功了,其实也可以不生成密钥,直接两两相乘,看看是不是等于n就行了。
这里可以看到,这两个数就是p和q,至于剩下的就不用管了,现在我们已经知道了私钥中的前两个数是p、q,一键不用管其他的是什么了,只要有这两个就够了。
根据这个方法来解析题目中的私钥
提取:p
D1665DB62A942E0DA238E97B0952FFFE4414790C2A50450EA5106F30C56A13ED430AF61F5753D1ACE747070A3EFDB8E5A2A017A44B92961C5A67BF45D0991BC6CC551C9FFF187F4A10E77E49740889AE1034A4EA1545A9365DFE326E031EA0F1E5142150969A2248D6C345BFC2A59A81095FBC929B8932A79F8ED3A427792EE7
提取:q
CB0781CFD32278BFE16A99D1E8E9B288D559846A7DF4D7FD484C2BA3A46CEECD6ADFBA3A731EE7CFA3B33533B83BD9FC660698C86EE3DFDF0D007FA2826196AD50B4C992653685749927FE665BE8B628FA2201532385DA97085BCFF4D0371D42B06206AA7FF4DB2E56123A67ACC5C30E4FBA75FBDC28977A9EEB0DE2C9AE445F
然后因为注释说了只支持65537,那么e就是65537,下面生成私钥解密即可。
-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEAphJQSpdwze2yAe+MKwk8yvkkjlj7CyA+6aB58dw5YNkNZ104
fNkUZ793+CN5JeiUl+PIE4Jk9vNMznxUKGMKuyivLFX4k2ghiIOA34A7aG0hZ3FX
8gLKaXK8mRKEw4MWAsrNofDmm8avnQzrEm+uO0KBcAXHMVb6JC4Piofq9k/VImGY
5wkZvwUdmDUvCgoFcOJexjmUHlqcA+pkY/ovXjVa8cD4/D+Y+PZAO/48lYZdjics
yIVW06XyC39gbCCdVx8ENnJHo6IvqsTbmCafqLS2cpQDZ0/KShv7kXImfQi6ptjG
JPBZ4UoMOxQyIVZfSvzDzQr5uQiDM0GGFm/DuQIDAQABAoIBAAMbUJk0oA2aJrxW
iN69O3/ojUCEdZ3Nqp+gOufFYOVo6hFG8ymSvgj60fm4YCnPYgg9YJ7Mz6q2/nbW
aJSg1bCOoEhKC25mgkoVe7GyqmnXsMpImoaSesriNJkAea9WonDG7nXbFdVQMDTV
6wfbQv0kz1sTIJjRsbg/jFbhGAoniHQIAuaOfkv6ShheB9Unj9t+99sPMtUpbab/
nAfn5Ivimrz+eyZjdeCw2DpGU04XWOdDl3Ar4xTohpdnM/8tOmQ1xOv6fu4p/3Pa
M8d5CCPZ9hTSgtPLSx3PoSO4INuRCGkSxZmtRJdPmJiCmVniH7G8tU7gXnYfpKV7
IEDIS4kCgYEA0WZdtiqULg2iOOl7CVL//kQUeQwqUEUOpRBvMMVqE+1DCvYfV1PR
rOdHBwo+/bjloqAXpEuSlhxaZ79F0JkbxsxVHJ//GH9KEOd+SXQIia4QNKTqFUWp
Nl3+Mm4DHqDx5RQhUJaaIkjWw0W/wqWagQlfvJKbiTKnn47TpCd5LucCgYEAyweB
z9MieL/hapnR6OmyiNVZhGp99Nf9SEwro6Rs7s1q37o6cx7nz6OzNTO4O9n8ZgaY
yG7j398NAH+igmGWrVC0yZJlNoV0mSf+Zlvotij6IgFTI4Xalwhbz/TQNx1CsGIG
qn/02y5WEjpnrMXDDk+6dfvcKJd6nusN4smuRF8CgYBIZ7H9nElyhypRrYHqnnV/
8QB3Ppqe+NHwh3c7EPf1/fNRpfr+UjBNLgdkSsmvJ7DXg63JFIySNSmZeAzm7Roq
qlq/tB8b1F/C6pjDQ0j0emiGG4QJaPXyo5uSynFvtM0Pnd9LI1gWhMMl8Ec3QdXj
yl79MGBxlz9Yr6VEvJVtfwKBgD7psJwJvODV9K/nwlf+Msib9AVISoeYdm/0yoEG
7oqBNODnAD20EfkRrPKLeEdzoPasjKNvWUWCBLFm26CzRNGn9J2Rs7NVX3AmKHrn
eBEaWYg4CN81Fys999VU80Bg3M1zUsV6qRFSJnG3j3DGR08j/Y+Z3/rkFacxBziD
bnDZAoGBAJ2BXcbcGojQ5w1ri8k5AEIpL8Fr8qNpjfSnJMMvi+A6bjedL+5XvYJv
0RDhu/SccE5WI2DHPdMze1l6+xOnlSepx1lp0u7muN9RICk6pQaasESnCExYg8PW
tl8bTmZq/QndTzgkgLU/M6Hd2p6eUO2W5eKKA6bEy4XFvVpMTc7O
-----END RSA PRIVATE KEY-----
下面补充源代码。
# -- coding: utf-8 --
# ShiKangsi
# [email protected]
import base64
import rsa,base64
class RSAFunc():
'''
pub_file: 公钥路径
pri_file:私钥路径
'''
def __init__(self,pub_file,pri_file):
self.pub_file_path=pub_file
self.pri_file_path=pri_file
def __getNE(self):
with open(self.pub_file_path, 'rb') as f:
# 读取n的长度
n_size = f.read(4)
# print(f.tell())
# f.seek(4)
# 读取n的值
n = f.read(int(n_size.hex(), 16)).hex()
# f.seek(4+int(n_size.hex(),16))
# 读取e的长度
e_size = f.read(4)
# 读取e的值
e = f.read(int(e_size.hex(), 16)).hex()
n = int(n, 16)
e = int(e, 16)
return n,e
def __getPQ(self):
with open(self.pri_file_path, 'rb') as f:
# 读取p的长度
# p_size = f.read(4)
f.seek(4)
p_size = b'\x00\x00\x00\x80'
# print(int(p_size.hex(), 16))
# 读取q的值
p = f.read(int(p_size.hex(), 16)).hex()
# 读取q的长度
q_size = f.read(4)
# f.seek(4+int(p_size.hex()))
# q_size = b'\x00\x00\x00\x80'
# 读取q的值
q = f.read(int(q_size.hex(), 16)).hex()
p = int(p, 16)
q = int(q, 16)
return p,q
def __extended_gcd(self,a, b):
if a == 0:
return (b, 0, 1)
else:
gcd, x, y = self.__extended_gcd(b % a, a)
return (gcd, y - (b // a) * x, x)
def __getD(self,e,p,q):
# n = p * q
phi = (p - 1) * (q - 1)
gcd, x, y = self.__extended_gcd(e, phi)
phi = (p - 1) * (q - 1)
d = x % phi
return d
def getPublicKey(self):
n,e=self.__getNE()
public_key = rsa.PublicKey(n, e)
return public_key
def getPrivateKey(self):
n,e=self.__getNE()
p,q=self.__getPQ()
d=self.__getD(e,p,q)
private_key = rsa.PrivateKey(n, e, d, p, q)
return private_key
def encrypt(self,msg,public_key):
return base64.b64encode(rsa.encrypt(msg.encode(),public_key)).decode('utf-8')
def decrypt(self,msg,private_key):
return rsa.decrypt(base64.b64decode(msg.encode()),private_key)
def saveKey(self,key,filename):
key=key.save_pkcs1()
with open(filename,"wb") as f:
f.write(key)
f.flush()
f.close()
def signMsg(self,msg,private_key,hashMethod):
return base64.b64encode(rsa.sign(msg.encode(), private_key, hashMethod)).decode("utf-8")
def verifyMsg(self,msg,sign,public_key):
try:
return rsa.verify(msg.encode(), base64.b64decode(sign), public_key)
except rsa.VerificationError as e:
return str(e)
if __name__ == '__main__':
# filename="20231229"
rsafunc=RSAFunc(r"\密钥对\20231229.pub",r"\密钥对\20231229.pri")
public_key=rsafunc.getPublicKey()
private_key=rsafunc.getPrivateKey()
rsafunc.saveKey(public_key,"20231229.pem")
rsafunc.saveKey(private_key,"20231229_pri.pem")
msg="mxpy{e119cbef54dc4e4fbd1b127a1007e1e3}"
print("待加密字符串:"+msg)
encmsg=rsafunc.encrypt(msg,public_key)
print(f"加密:{encmsg}")
print(f"解密:{rsafunc.decrypt(encmsg,private_key).decode('utf-8')}")
# s="aWi4LwpVdhn65sjVnMcVR4nvt1DWAznrL/go+cVwy+k9zCMQMGlp2rWJOn7ohwgwufmREjhniLP4lAucOQTHM2+KtnmYFZ0Sw1sXygnsq57YhGlySbJWV9O0OrQl6cJZgMEAKV5Re5IfsYaPKwzFZxGwRXPhKwaMhhgoCHIfwF5RrSQslHGS/RCPTakrXi71+BwL27hrL/tFFHiN/y5FZCnz7+99s4eVc29GYmejijWVp/V76P4g1FHXk+GcaPhs+6TVv8CJkxl/hTtvKWhrD5Rd0ubx+xN92a5BucgwJS+3j5xdgoHXa2ZhvhBWoB1WFWcnP/UYnSI5FkVxerfM9w=="
# print(f"解密:{rsafunc.decrypt(s,private_key).decode('utf-8')}")
sign=rsafunc.signMsg(msg,private_key,"SHA-256")
print(f"签名:{sign}")
print(f"校验:{rsafunc.verifyMsg(msg,sign,public_key)}")
结束,点击原文跳转到公告页面。