元旦解题游戏-第一题write up
2024-1-14 09:33:22 Author: F12sec(查看原文) 阅读量:10 收藏

前言

    今天公开元旦解题活动第一题答案,感谢大家的参与。

第一题 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# [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)}")

    结束,点击原文跳转到公告页面。


文章来源: http://mp.weixin.qq.com/s?__biz=Mzg5NjU3NzE3OQ==&mid=2247488803&idx=1&sn=37c40f405cde7a1fa22eb97ba9e2a18f&chksm=c18cd925d7b510c5f0f8a2627482dc5187de77aa0bb6d690eda155b3f1bb75a1dfccafb6cafe&scene=0&xtrack=1#rd
如有侵权请联系:admin#unsafe.sh