20240112-元旦解题游戏-第一题
前言
今天公开元旦解题活动第一题答案，感谢大家的参与。
第一题 write up
提示已经给的很明显了，就是RSA算法
下面给出RSA基本原理
找出两个不同的素数p、qn = 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字节的信息，以此类推会获得下面几个值：
FB0BAD128CC8E130A7BF98D83B9DEC28B4A919CA530B29D9C3D642C2B92502610B445871D0D190B8B1508733D928F96DD3894EBC3E6289ECBEDEBAC009D780567C292AAC05486E0BBE481D73A271203E882A135D08214838FE508BF35F5C00A17155535B1AFA41959299A006A531917B74F6A86DD735696228EE47CA89BE9137D304628A2429B7B3A701B6BE76F2434D9EAB5DDABD44D1AFCD6E49AC1227C8D0A62861F0DF134B7DCBC543A6BEFACDA589A0084DF2655CE4930BA73D7CB523934E4A4C35512508B831D62E67CD3A2450CA2402E67DB030D87CDE4F6A8F9A44C5617337311FAB13EB4CD610F853924AB9B44275AC7447E02D005B4FDB26455FD3449A23387F7A61773F4FEF3F9FC2FF06FC9F7D29B9D9C21CFD142EF83149F8C57623BE1B9419C0778814DE6D7FB95FB7F067843992BEB0BC1E489535E73A999A88A16344D0C8C331B854D29F87D36C214A6A5D123E278229F8ED1FE168BCA67B7791FE8E55E7EF4625628FC5611D13896E23FD50CECF8CB5C343A220A9D586AF719EF2D01F18B7696C8B67B2B6A94BC407A38E2DB1ABD49C2CA92DD211148AF48E0340794A244189C2A6BCFE93E6C7C4528E70EA47927CAA36E31771EC2C3CB39C7C34FCA06CA87D459865F44E74F808E84EEBA0E01C76B09ACBB9474F7B697C3E34A38B37DA0E27AC7FB7337F0C4E601FC789450A778925B20378C42F9F3B318568AFFBA18833933CF3E26933D66F84042495EF309B23124001993F27645F603961E4982E2EC54B13B1F37E64B6F9CD32488E78A2147965B347EB3B89CFB833E89129588693B4996E0A71C7EFF9CEF56E2B67679ACBBE02566698E70BDC574F92E6CD3513CA7E42FB5866C627FAE204D48CB66111E2BDC3A27041AA7DDD7F76
这里明显有个问题，出现了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+6aB58dw5YNkNZ104fNkUZ793+CN5JeiUl+PIE4Jk9vNMznxUKGMKuyivLFX4k2ghiIOA34A7aG0hZ3FX8gLKaXK8mRKEw4MWAsrNofDmm8avnQzrEm+uO0KBcAXHMVb6JC4Piofq9k/VImGY5wkZvwUdmDUvCgoFcOJexjmUHlqcA+pkY/ovXjVa8cD4/D+Y+PZAO/48lYZdjicsyIVW06XyC39gbCCdVx8ENnJHo6IvqsTbmCafqLS2cpQDZ0/KShv7kXImfQi6ptjGJPBZ4UoMOxQyIVZfSvzDzQr5uQiDM0GGFm/DuQIDAQABAoIBAAMbUJk0oA2aJrxWiN69O3/ojUCEdZ3Nqp+gOufFYOVo6hFG8ymSvgj60fm4YCnPYgg9YJ7Mz6q2/nbWaJSg1bCOoEhKC25mgkoVe7GyqmnXsMpImoaSesriNJkAea9WonDG7nXbFdVQMDTV6wfbQv0kz1sTIJjRsbg/jFbhGAoniHQIAuaOfkv6ShheB9Unj9t+99sPMtUpbab/nAfn5Ivimrz+eyZjdeCw2DpGU04XWOdDl3Ar4xTohpdnM/8tOmQ1xOv6fu4p/3PaM8d5CCPZ9hTSgtPLSx3PoSO4INuRCGkSxZmtRJdPmJiCmVniH7G8tU7gXnYfpKV7IEDIS4kCgYEA0WZdtiqULg2iOOl7CVL//kQUeQwqUEUOpRBvMMVqE+1DCvYfV1PRrOdHBwo+/bjloqAXpEuSlhxaZ79F0JkbxsxVHJ//GH9KEOd+SXQIia4QNKTqFUWpNl3+Mm4DHqDx5RQhUJaaIkjWw0W/wqWagQlfvJKbiTKnn47TpCd5LucCgYEAyweBz9MieL/hapnR6OmyiNVZhGp99Nf9SEwro6Rs7s1q37o6cx7nz6OzNTO4O9n8ZgaYyG7j398NAH+igmGWrVC0yZJlNoV0mSf+Zlvotij6IgFTI4Xalwhbz/TQNx1CsGIGqn/02y5WEjpnrMXDDk+6dfvcKJd6nusN4smuRF8CgYBIZ7H9nElyhypRrYHqnnV/8QB3Ppqe+NHwh3c7EPf1/fNRpfr+UjBNLgdkSsmvJ7DXg63JFIySNSmZeAzm7Roqqlq/tB8b1F/C6pjDQ0j0emiGG4QJaPXyo5uSynFvtM0Pnd9LI1gWhMMl8Ec3QdXjyl79MGBxlz9Yr6VEvJVtfwKBgD7psJwJvODV9K/nwlf+Msib9AVISoeYdm/0yoEG7oqBNODnAD20EfkRrPKLeEdzoPasjKNvWUWCBLFm26CzRNGn9J2Rs7NVX3AmKHrneBEaWYg4CN81Fys999VU80Bg3M1zUsV6qRFSJnG3j3DGR08j/Y+Z3/rkFacxBziDbnDZAoGBAJ2BXcbcGojQ5w1ri8k5AEIpL8Fr8qNpjfSnJMMvi+A6bjedL+5XvYJv0RDhu/SccE5WI2DHPdMze1l6+xOnlSepx1lp0u7muN9RICk6pQaasESnCExYg8PWtl8bTmZq/QndTzgkgLU/M6Hd2p6eUO2W5eKKA6bEy4XFvVpMTc7O-----END RSA PRIVATE KEY-----
下面补充源代码。
# -- coding: utf-8 --# ShiKangsi# admin@sg95.cnimport base64import rsa,base64class 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)}")
结束。