跳转至

RSA例题

前言

在我们在做CTF的密码学解题时,我们经常能发现,题型无非就是对称密码、不对称密码这些老生常谈的考点,RSA更是出题人最喜欢的知识点。那么什么是RSA,让我们用浅显的语言和题目来初步认识吧!由于自身只是一名初级选手,在讲述的过程中如有不准确甚至错误的地方,还望各路大牛批评指正!

正文

RSA算法介绍

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

RSA的算法涉及三个参数,n、e1、e2。

其中,n是两个大质数p、q的积,n的二进制表示时所占用的位数,就是所谓的密钥长度。

e1和e2是一对相关的值,e1可以任意取,但要求e1与(p-1)*(q-1)互质;再选择e2,要求

(e2×e1)1(mod(p-1)×(q-1))

(n,e1),(n,e2)就是密钥对。其中(n,e1)为公钥,(n,e2)为私钥。

RSA加解密的算法完全相同,设A为明文,B为密文,则:

AB^e2( mod n)BA^e1 (mod n)

(公钥加密体制中,一般用公钥加密,私钥解密)

e1和e2可以互换使用,即:

AB^e1 (mod n)BA^e2( mod n)

RSA加解密算法

小结一下上文

密文=明文的e指数 mod n 公钥 = (e,n)

明文=密文的d指数 mod n 私钥 = (d,n)密钥对 (e,d n)

求n

准备两个质数p,q。这两个数不能太小,太小则会容易破解,将p乘以q就是n

n=p × q

求L

L 是 p-1 和 q-1的最小公倍数

L= lcm ( p -1 q - 1

求e

E必须满足两个条件:E是一个比1大比L小的数,E和L的最大公约数为1

用gcd(X,Y)来表示X,Y的最大公约数则E条件如下

1 < e < L
gcd ( e , L ) =1

求d

求D也必须满足2个条件:

1 < d < Le × d mod L  1

CTF RSA 算法题目详细讲解

第一题 已知p、q、e求d

题目链接 : http://www.shiyanbar.com/ctf/1828

题目描述:

p = 473398607161
q = 4511491
e = 17

 d
此题告诉我们 p、 q 、e

根据上面的方式求 d 脚本附下

安装好gmpy2库,python搞定:

p, q, e = gmpy2.mpz(473398607161), gmpy2.mpz(4511491), gmpy2.mpz(17)
    phi_n = (p - 1) * (q - 1)
    d = gmpy2.invert(e, phi_n)
    print d

第二题 已知p、q、e和密文 求明文

题目链接 : http://www.shiyanbar.com/ctf/1979

题目:

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

c 是密文 已知 p、q、e 求明文

由上文得先求d 然后用解密的上文 数学公式 python 脚本附下

import gmpy2

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

phi = (p - 1) * (q - 1)
# 计算得到私钥(n, d)

d = long(gmpy2.invert(e, phi))

n = p * q
# 计算并输出c^d mod n

print pow(c, d, n)

第三题 已知n、e和密文 求明文

题目链接 : http://www.shiyanbar.com/ctf/1918

{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

从题目中已经得 n 和e

然后这里我们可以有几种方法求得p、q

因式分解 n 用yafu

使用yafu-1.34

yafu使用方法

使用cmd进入yafu的解压目录(为了方便的话,自己可以把该目录加入到环境变量。)

输入yafu-x64进入命令行

最常用的命令是factor(n),将n值分解

得到p q 后求d 用 c(密文)的d次方模n得到明文

分解求得 n e 我们也可以用 github 上面的一个开源项目 求d

分解公钥得n、e的值,然后求解d,也可以用维纳攻击求d

Python 脚本

#快速幂取模
def expMod2 (x, y, k ):  
    MASK = 0xffffffff  
    tx = x  
    modRes = 1  
    tx %= k  

    while (y&MASK):  
        if (y&1):  
            modRes = modRes * tx % k;

        y = (y>>1);  
        tx = tx * tx % k;  
    return modRes  

def toStr(i):
    result = ""
    while i!=0:
        result = chr(i % 256) + result
        i = i/256
    return result

B = [
     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, 
     ]
n = 920139713
d = 96849619
result = ""
for b in B:
    a = expMod2(b, d, n)
    result += toStr(a)

print result

第四题 已知公钥文件和密文文件,求明文

fujian.zip title 已知公钥文件,先用openssl求出e和n

openssl rsa -pubin -text -modulus -in public.key

-pubin   表示输入的文件是公钥
-text    打印出e
-modulus 打印出n
-in      输入文件
title 可得e为65537 n为16进制数D99E952296A6D960DFC2504ABA545B9442D60A7B9E930AFF451C78EC55D555EB python专为10进制即98432079271513130981267919056149161631892822707167177858831841699521774310891 title 用yafu或登录http://factordb.com进行因式分解 title 求得 p=302825536744096741518546212761194311477 q=325045504186436346209877301320131277983 用rsa模块进行解密
import gmpy2,rsa

p = 302825536744096741518546212761194311477
q = 325045504186436346209877301320131277983
n = 98432079271513130981267919056149161631892822707167177858831841699521774310891
e = 65537
d = int(gmpy2.invert(e , (p-1) * (q-1)))

privatekey = rsa.PrivateKey(n , e , d , p , q)      #根据已知参数,计算私钥

with open("encrypted.message1" , "rb") as f:
    print(rsa.decrypt(f.read(), privatekey))       #使用私钥对密文进行解密,并打印
with open("encrypted.message2" , "rb") as f:
    print(rsa.decrypt(f.read(), privatekey))       #使用私钥对密文进行解密,并打印
with open("encrypted.message3" , "rb") as f:
    print(rsa.decrypt(f.read(), privatekey))       #使用私钥对密文进行解密,并打印

第五题 已知公钥,密文,n很难分解,但e很大

例题:Vulnerable RSA.zipopenssl从公钥中提取ne

openssl rsa -pubin -text -modulus -in rsa_public_key.pem
或者用rsatools中的RsaCtfTool.py求n和e
python RsaCtfTool.py --pkey rsa_public_key.pem
title 尝试用yafu-x64分解n得不到结果 由于e很大,使用维纳攻击,rsa-wiener-attack-master.zip title 得到d为8264667972294275017293339772371783322168822149471976834221082393409363691895 再用rsatools中的rsatool.py求得私钥 title 或使用RDLP.exe: title
python rsatool.py -d 8264667972294275017293339772371783322168822149471976834221082393409363691895 -n 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597 -e 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619 -o pri
最后用openssl解密:
openssl rsautl -decrypt -in flag.enc -inkey pri
title

第六题 已知两个E值,共一个N值

例题veryhardRSA.zip 采用共模攻击,直接上脚本

#coding=utf-8
#RSA 共模攻击
import gmpy2
from libnum import s2n,n2s

n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929
e1 = 17
e2 = 65537
with open('flag.enc1','rb') as file1:
    c1 = s2n(file1.read())
with open('flag.enc2','rb') as file2:
    c2 = s2n(file2.read())

s = gmpy2.gcdext(e1,e2)
s1 = s[1]
s2 = -s[2]
c2 = gmpy2.invert(c2, n)
m = (pow(c1,s1,n) * pow(c2 , s2 , n)) % n

print m # flag可能是m值的10进制每2至3位转成字符

flag = n2s(m) # 也可能是m值转16进制再转字符
print flag # 可能直接转出明文
with open('flag','wb') as file3:
    file3.write(flag) #也能转出不可见字符但其中夹杂着flag