从零开始学RSA：低加密指数分解攻击

RSA是一种非对称加密算法，它由 公钥（n/e），私钥(n/d)，明文M和密文C组成。我们做CTF题目时，一般题目中会给出公钥和密文让我们推出对应的私钥或者明文。RSA的相关公式都写在上面脑图中，在正式讲解RSA加密算法前我们先来普及一波数学的基本知识。

一. 相关数学基础

1.1  素数和互质数

素数也称质数，它的定义为除本身和 1 的乘积外，不能表示其他数的乘积。比如2，3，5，7，11，13，17……等都是素数。

互素数也称互质数，定义是公约数只有1的两个自然数，如：

1和任何自然数 1 & 2

任意 2个质数 2 & 3

相邻2个自然数 4 & 5

3 & 10 、7 & 10 、5 & 26等等。

1.2  模指数运算

模运算就是取余数，如5 mod 3 =2。而模指数就是，先做指数运算在做mod运算。

如：53 mod 7 = 125 mod 7 =6

我们可以使用python的pow()来求解模指数运算。

1.3  同余运算

两个整数a,b，它们除以整数M所得的余数相等：a ≡ b(mod m)，比如说5除3余数为2，11除3余数也为2，于是可写成11 ≡ 5(mod 3)。

二. RSA加密算法

2.1 加解密算法

前面已经说过，RSA是一种非对称加密算法，这个算法的特点就是明文使用公钥进行加密得到密文，而密文解密使用私钥来解。

所需的密钥对为n,d,e。密钥对是如何生成的？

2.2 生成密钥对

密钥对的生成步骤如下：n → L→e→d （L作为生成过程中的中间数）。

三. CTF题目实战

3.1  已知p、q、e求d

RSA题目1

p= 18255878996579787209

q= 324206965464727676218470615969477348407

e= 13

此题直接告诉我们p、q、e，让我们求解d

直接使用脚本进行实现。

import math
def getEuler(p1,q1):
    return (p1-1)*(q1-1)
def getDkey(e,Eulervalue):
    k=1
    while True:
        if ((Eulervalue*k)+1)%e==0:
            (d,m)=divmod(Eulervalue*k+1,e)
            return d
        k += 1
def Mingwen(c,d,n):
    return pow(c,d,n)
if __name__=='__main__':
    p=18255878996579787209
    q=324206965464727676218470615969477348407
    d=getDkey(13,getEuler(p,q))
    print('私钥为:%d'%d)

私钥为:4552833177978761857275087159381075983327579204175044608037

import gmpy2
p= 18255878996579787209
q= 324206965464727676218470615969477348407
e= 13
phi_n= (p - 1) * (q - 1)
d = gmpy2.invert(e, phi_n)
print("d is:")
print (d)

d is: 4552833177978761857275087159381075983327579204175044608037

将获取的d，进行md5加密：d3ba43fb7bbe17d17aa7054a7ed3ac23，得到的结果即为flag。

3.2 已知p、q、e和密文 求明文

 题目：

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

数学很酷！使用RSA算法解码秘密消息，其中c、p、q和e是RSA算法的参数。

p =  9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483

q =  11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407

e =  65537

c =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

Use RSA to find the secret message

使用RSA算法找出秘密消息。

1.读题：(N,d)是私钥，(N,e)是公钥，公钥加密，私钥解密，c是密文，求明文

————————————————基础知识回顾—————————————————————

p , q 是任选大素数

n=p*q      φ(n) =(p-1)*(q-1)

e*d=1modφ(n)         (e*d)modφ(n)=1

加密：Sig(x)=x^e mod n

解密：x=Sig(x)^d mod n

———————————————————————————————————————————

本题答案为：flag{5577446633554466577768879988}

2.第一步：求n，n=p*q

N=114573516752272714750064227635008832737477859608443481000717283425702025029279291376859256856603741797722497252841363753834114679306784379319341824813349417007577541466886971550474580368413974382926969910999462429631003527365143148445405716553105750338796691010126879918594076915709977585368841428779903869581

3.第二步：求φ(n)：φ(n) = (p - 1) * (q - 1)

φ=114573516752272714750064227635008832737477859608443481000717283425702025029279291376859256856603741797722497252841363753834114679306784379319341824813349395484310674476074262867516991704330586676279176131878754135601460783229276940745427904455048854467754090254652258775177617277116136508905378817444751921692

4. 第三步：求私钥指数（d）：(e*d)modφ(n)=1

d=56632047571190660567520341028861194862411428416862507034762587229995138605649836960220619903456392752115943299335385163216233744624623848874235303309636393446736347238627793022725260986466957974753004129210680401432377444984195145009801967391196615524488853620232925992387563270746297909112117451398527453977

5.第四步：解密消息（M）：M = c^d mod n

m=5577446633554466577768879988

So，答案为：flag{5577446633554466577768879988}

import gmpy2

p =  9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =  11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =  65537
c =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
s = (p-1)*(q-1)
d = gmpy2.invert(e,s)
n = p*q
m = pow(c, d, n)   # m 的十进制形式
string = long_to_bytes(m)  # m明文
print(string)  # 结果为 b‘ m ’ 的形式
print(m)
print(d)
print(n)

m

5577446633554466577768879988

d

56632047571190660567520341028861194862411428416862507034762587229995138605649836960220619903456392752115943299335385163216233744624623848874235303309636393446736347238627793022725260986466957974753004129210680401432377444984195145009801967391196615524488853620232925992387563270746297909112117451398527453977

n

114573516752272714750064227635008832737477859608443481000717283425702025029279291376859256856603741797722497252841363753834114679306784379319341824813349417007577541466886971550474580368413974382926969910999462429631003527365143148445405716553105750338796691010126879918594076915709977585368841428779903869581

3.3 已知n、e和密文 求明文

题目描述：

data：

{920139713,19}

704796792

752211152

274704164

18414022

368270835

483295235

263072905

459788476

483295235

459788476

663551792

475206804

459788476

428313374

475206804

459788476

425392137

704796792

458265677

341524652

483295235

534149509

425392137

428313374

425392137

341524652

458265677

263072905

483295235

828509797

341524652

425392137

475206804

428313374

483295235

475206804

459788476

306220148

{920139713,19} 是公钥 {n,e}

先分解n，然后通过脚本得到flag

import gmpy2
p = 18443
q = 49891
e = 19
n = 920139713
d = gmpy2.invert(e,(p-1)*(q-1))
c = [704796792,752211152,274704164,18414022,368270835,483295235,263072905,459788476,483295235,459788476,663551792,475206804,459788476,428313374,475206804,459788476,425392137,704796792,458265677,341524652,483295235,534149509,425392137,428313374,425392137,341524652,458265677,263072905,483295235,828509797,341524652,425392137,475206804,428313374,483295235,475206804,459788476,306220148,]
flag = ''
for i in c:
    x = pow(i,d,n)
    flag += chr(x)
print(flag)

flag{13212je2ue28fy71w8u87y31r78eu1e2}