RSA

题目

在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17
求解出d作为flag提交

解题思路

在密码学相关计算中，可利用python的gmpy2库，非常方便

附上代码：

import gmpy2
p =9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
d = gmpy2.invert(e, (q-1)*(p-1))
print(d)

flag

flag{125631357777427553}

知识点

RSA加密

参数pqde，公开n,e，秘密保存d

• 1.n=pq，fai(n)=(p-1)(q-1)，fai()指欧拉函数
• 2.(de)mod(fai(n)) = 1，即de = k(fai(n))+1

加密
c = m^e mod n
解密
m = c^d mod n

gmpy2库的常用函数

• gmpy2.mpz(n)#初始化一个大整数
• gmpy2.mpfr(x)# 初始化一个高精度浮点数x
• d = gmpy2.invert(e,n) # 求逆元，de = 1 mod n
• C = gmpy2.powmod(M,e,n)# 幂取模，结果是 C = (M^e) mod n
• gmpy2.is_prime(n) #素性检测
• gmpy2.gcd(a,b) #return r 其中，r为a和b的最大公约数
• gmpy2.gcdext(a,b) #扩展欧几里得算法，return (r,x,y) 其中，r为a和b的最大公约数，满足ax + by = 1
• gmpy2.iroot(x,n) #x开n次根

rsarsa

题目

Math is cool! Use the RSA algorithm to decode the secret message, c, p, q, and e are parameters for the RSA algorithm.

p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

Use RSA to find the secret message

解题思路

这道题是最基础的RSA题，p,q,e,c全部给出，直接计算出私钥d，再进行解密即可

其中，d为e(mod φ(n))的逆元，即d * e = 1 + k * φ(n)

gmpy2库中的gmpy2.invert()可以计算逆元

附上代码：

import gmpy2
p =9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
n = p * q
c =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

d = gmpy2.invert(e, (q-1)*(p-1))#计算逆元
m = gmpy2.powmod(c,d,n)#解密m = c^d % n
print("flag{%d}" % m)

flag

flag{5577446633554466577768879988}

RSAROLL

题目

RSA roll！roll！roll！
Only number and a-z（don’t use editorwhich MS provide）

{920139713,19}

另给出 data.txt

解题思路

{920139713,19}给出了公钥{n, e}

公钥很短，直接爆破分解就行了

这里分解的具体思路为：

• 假设p = x + y，q = x - y，则n = p * q = x² - y²，这里可以确定x² > n
• 然后直接从√n往上遍历寻找x
• 令y = √(x² - n)
• 若p = x + y，q = x - y满足：n = p * q且均为素数，就证明分解成功

分解完后，计算私钥d，再对data.txt中的密文进行解密即可得到flag

附上代码：

import gmpy2
    
#因数分解,返回值分别为n的因数
def Factorization(n):
    x = gmpy2.iroot(n,2)[0] + 1 #gmpy2.iroot(x,n) #x开n次根
    while(True):
        y2 = x * x - n
        y = gmpy2.iroot(y2,2)[0]
        p, q = x + y, x - y
        if (p) * (q) == n:
            if gmpy2.is_prime(p) and gmpy2.is_prime(q): #素性检测
                return (p, q)
        x = x + 1
        
if __name__ == "__main__":
    n, e = 920139713, 19
    p, q = Factorization(n)
    print("N的分解结果为 : ")
    print("%d = %d * %d" % (n, p, q))
    d = gmpy2.invert(e,(p-1)*(q-1)) # 求私钥d，d为e的逆元
    with open("./data.txt","r") as f:
        for line in f.readlines():
            line=line.strip('\n')#去掉列表中每一个元素的换行符
            print(chr(gmpy2.powmod(int(line),d,n)), end = '')

flag

flag{13212je2ue28fy71w8u87y31r78eu1e2}

RSA(latter)

题目

这个题目名字也叫RSA，和前面那道重合了，故用(latter)加以区分

题目给出两个文件，分别是

• flag.enc
  
• pub.key
  

解题思路

这里给出的pub.key明显是一个公钥文件

放到网站上提取公钥http://tool.chacuo.net/cryptrsakeyparse，提取得到

e = 65537
n = 86934482296048119190666062003494800588905656017203025617216654058378322103517

这是一个256bit的n，用前面的爆破代码效率很低

君子生非异也，善假于物也

因此需要用到一个分解模数的网站http://www.factordb.com，分解得到

p = 285960468890451637935629440372639283459
q = 304008741604601924494328155975272418463

至此，参数齐活了，然后计算私钥d进行解密即可

附上代码：

import gmpy2
import binascii

e = 65537
n = 86934482296048119190666062003494800588905656017203025617216654058378322103517
p = 285960468890451637935629440372639283459
q = 304008741604601924494328155975272418463
d = gmpy2.invert(e,(p-1)*(q-1)) #求私钥d，d为e的逆元

with open("flag.enc", "rb+") as f:
    c = f.read()    #读取密文
c = int.from_bytes(c, byteorder='big', signed=False)    #byte类型数据转十进制

m = gmpy2.powmod(c,d,n) # 幂取模，求明文
m = hex(m)[2:]     
print("明文数据为：0x" + m)
flag = binascii.unhexlify('0' + m)

print(flag)

运行之后，得到b’\x02\x9d {zR\x1e\x08\xe4\xe6\x18\x06\x00flag{decrypt_256}\n’

这里有一个小坑，直接令flag = binascii.unhexlify(m)会报错，因为m是一个奇数长度的字符串，所以让它前面加了一个’0’，当然加一个’1’也是一样的。另外，不清楚为什么前面会多出一些乱码，知道的同学可以评论区解释一下。

flag

flag{decrypt_256}