元旦解题游戏-第一题write up

元旦解题游戏-第一题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，下面生成私钥解密即可。

下面补充源代码。

# -- 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