RSA

Author Avatar
Righteous 1月 02, 2017

简介

RSA公钥加密算法是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（AdiShamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。1987年首次公布，当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。
RSA算法基于一个十分简单的数论事实：将两个大质数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。 RSA 的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。人们已能分解多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。

数论知识

  • 互质关系
  • 欧拉函数
  • 欧拉定理
  • 欧拉准则
  • 中国剩余定理
  • 模反元素

算法原理

1.随机选择两个不相等的质数p,q
2.计算p和q的乘积n
3.计算n的欧拉函数φ(n)=(p-1)(q-1)
4.随机选择一个整数e,条件是1<e<φ(n),且e与φ(n)互质
5.计算e与φ(n)的模反元素d
6.将n与e封装成公钥(n,e)，将n与d封装成私钥(n,d)

加解密

加密

用公钥(n,e),对m进行加密，得到密文c

c ≡ me mod n

例：已知公钥(920139713,19),对明文m加密后得到密文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]

解密

用私钥(n,d),对c进行解密，得到明文m

m ≡ cd mod n

思路：分解n,求p,q,进而得到d,对密文c解密得到明文m
解密代码：

import gmpy2
char=[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
p = 18443
q = 49891
e = 19
d = gmpy2.invert(e,(p-1)*(q-1))
for c in char:
    print ('%x' % pow(c,d,n)).decode('hex')

解得明文m：flag{13212je2ue28fy71w8u87y31r78eu1e2}

CTF之RSA

Tools

  • factordb，Sagemath，yafu
  • openssl
  • python gmpy2
  • rsatool

Problems

题目来源：
http://www.jarvisoj.com
http://www.ichunqiu.com/racing/54627

very easy RSA

已知RSA公钥生成参数：
p = 3487583947589437589237958723892346254777
q = 876786784356893476598347658437658389
e = 65537
求d =
(1)

q = 876786784356893476598347658437658389
e = 65537  
t = (p-1)*(q-1)   
i=0  
while True :   
    if (1-t*i)%e == 0:   
        break   
    i-=1   
    #print i 
print 'd=' + '%d' % ((1-t*i)/e)

(2)python gmpy2模块解决

p = 3487583947589437589237958723892346254777 
q = 876786784356893476598347658437658389
e = 65537  
d = gmpy2.invert(e,(p-1)*(q-1)) 
print d

(3）RSAtool
https://github.com/ius/rsatool

easy RSA

已知一段RSA加密的信息为：0xdc2eeeb2782c且已知加密所用的
公钥：(N=322831561921859,e = 23),求加密字符串
N分解为13574881*23781539

import gmpy2
n = 322831561921859
p = 13574881
q = 23781539 
e = 23 
c = int('0xdc2eeeb2782c',16)
d = gmpy2.invert(e,(p-1)*(q-1)) 
print ('%x' % pow(c,d,n)).decode('hex')

medium RSA

已知flag.enc和pubkey.pem
提取公钥
1.利用python的Crypto

from Crypto.PublicKey import RSA
A = RSA.importKey(open('pubkey.pem').read())
print 'N:' + '%d' % A.n
print 'e:' + '%d' % A.e

N:87924348264132406875276140514499937145050893665602592992418171647042491658461
e:65537

2.openssl

openssl rsa -pubin -text -modulus -in warmup -in pubkey.pem
Public-Key: (256 bit)
Modulus:
    00:c2:63:6a:e5:c3:d8:e4:3f:fb:97:ab:09:02:8f:
    1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f:
    be:30:dd
Exponent: 65537 (0x10001)
Modulus=C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
writing RSA key
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMJjauXD2OQ/+5erCQKPGqxsC/bNPXDr
yigb/+l/vjDdAgMBAAE=
-----END PUBLIC KEY----

3.yafu分解N

factor(87924348264132406875276140514499937145050893665602592992418171647042491658461)
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits

starting SIQS on c77: 87924348264132406875276140514499937145050893665602592992418171647042491658461

==== sieving in progress (1 thread):   36224 relations needed ====
====           Press ctrl-c to abort and save state           ====


SIQS elapsed time = 1.9607 seconds.
Total factoring time = 2.0212 seconds


***factors found***

P39 = 319576316814478949870590164193048041239
P39 = 275127860351348928173285174381581152299
ans = 1

import libnum
import gmpy2
f = open('flag.enc','r')
c = f.read()
c = libnum.s2n(c)
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
e = 65537
d = gmpy2.invert(e,(p-1)*(q-1))
n = p*q
r = pow(c,d,n)
print libnum.n2s(r%n)

hard RSA(Rabin密码)

N=87924348264132406875276140514499937145050893665602592992418171647042491658461
e=2
Rabin密码
加密：c = m2 mod n
解密：m2 = c mod n
n的值为公钥，p和q为私钥,n是可以分解的,分解后可以得到p,q。

import libnum
import gmpy2
f = open('flag.enc','r')
c = f.read()
c = libnum.s2n(c)
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
n = p*q
r = pow(c,(p+1)/4,p)
s = pow(c,(q+1)/4,q)
a = gmpy2.invert(p,q)
b = gmpy2.invert(q,p)
x =(a*p*s+b*q*r)%n
y =(a*p*s-b*q*r)%n
print libnum.n2s(x%n)
print libnum.n2s((-x)%n)
print libnum.n2s(y%n)
print libnum.n2s((-y)%n)

very hard RSA

分析加密脚本，使用了相同的N,不同的e,加密相同的数据,且两个加密指数互素，可以通过共模攻击在两个密文和公钥被嗅探的情况下还原出明文m的值

两个加密指数互质(e1,e2)=1,即存在s1,s2使得s1e1+s2e2=1
c1 ≡ me1 mod n
c2 ≡ me2 mod n
即 c1s1 c2s2 ≡ m mod n

from libnum import n2s,s2n
from gmpy2 import invert
n=0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L
def egcd(a, b):
  if a == 0:
    return (b, 0, 1)
  else:
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)
fo1 = open('flag.enc1', 'rb')
fo2 = open('flag.enc2', 'rb')
datafo1 = fo1.read()
c1 = s2n(datafo1)
fo1.close()
datafo2 = fo2.read()
c2 = s2n(datafo2)
fo2.close()
c2 = invert(c2,n)
e1 = 17
e2 = 65537
s = egcd(e1,e2)
s1 = s[1]
s2 = s[2]
s2 = - s2
m = pow(c1, s1, n) * pow(c2, s2, n) % n
print n2s(m)

Extremely hard RSA

解pubkey.pem发现N特别大，但e=3,可以进行低加密指数攻击
在RSA中e也称为加密指数。由于e是可以随意选取的，选取小一点的e可以缩短加密时间，但是选取不当的话，就会造成安全问题。

当e=3时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文三次开方，即可得到明文。
即：c ≡ me mod n

如果e=3，且me < n,
那么：c = me , e=3

如果明文的三次方比n大，但是不是足够大，那么设k，
有：c ≡ me +kn
爆破k,如果c−kn能开三次根式，那么可以直接得到明文。

from libnum import s2n,n2s
from gmpy2 import iroot
n=0xB0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
e = 3
f = open('flag.enc','rb')
c= f.read()
c = s2n(c)
f.close()
i = 0
while 1:
    res = iroot(c+i*n,3)
    if(res[1] == True):
        print res
        break
    print "i="+str(i)
    i = i+1

m=440721643740967258786371951429849843897639673893942371730874939742481383302887786063966117819631425015196093856646526738786745933078032806737504580146717737115929461581126895844008044713461807791172016433647699394456368658396746134702627548155069403689581548233891848149612485605022294307233116137509171389596747894529765156771462793389236431942344003532140158865426896855377113878133478689191912682550117563858186
print n2s(m)

参考：

http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html

http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

http://bobao.360.cn/learning/detail/3058.html

http://bestwing.me/2016/09/10/Common%20types%20of%20RSA/

http://www.bystudent.com/?p=234