获取中...

-

Just a minute...

RSA是一种既能用于数据加密也能用于数字签名的算法,是一种非对称加密算法,由公钥(n/e),私钥(n/d),明文m和密文c组成

算法原理

①选两个素数p和q(为了安全性,两数的长度一样)
②计算n=pq(n是模)
③计算欧拉函数(Euler):f(n)=(p-1)(q-1) ——> e与f(n)互质 1<e<f(n)——–>定义是公约数只有1的两个自然数
④选取密钥e,密钥常用值为3,17,65537(2¹⁶+1)
④求出e模ϕ(n)的逆元d:de≡1 mod f(n) d ≡e-¹ mod f(n)
⑤加密m:c≡m^e mod n
⑥解密c:m≡c^d mod n
mod就是取余,比如 5 mod 4 = 1, 9 mod 4 = 1,即 5 ≡ 9(mod 4)
1 mod 任何数都是1

rsa是一种非对称加密,明文使用公钥进行加密得到密文,密文使用私钥进行解密得到明文。

常见的互质

(1)两个质数一定是互质数。例如,2与7、13与19。
(2)一个质数如果不能整除另一个合数,这两个数为互质数。例如,3与10、5与 26。
(3)1不是质数也不是合数,它和任何一个自然数在一起都是互质数。如1和9908。
(4)相邻的两个自然数是互质数。如 15与 16。
(5)相邻的两个奇数是互质数。如 49与 51。
(6)大数是质数的两个数是互质数。如97与88。
(7)小数是质数,大数不是小数的倍数的两个数是互质数。如 7和 16。
(8)两个数都是合数(二数差又较大),小数所有的质因数,都不是大数的约数,这两个数是互质数。如357与715,357=3×7×17,而3、7和17都不是715的约数,这两个数为互质数。等等。

已知p,q,e,求d

p=3,q=11,e=3
ed≡ 1 (mod (P-1)(q-1))
y = invmod(x,p),使得x * y == 1(mod p)

1
2
3
4
5
6
7
8
import gmpy2
p = gmpy2.mpz(3)
q = gmpy2.mpz(11)
e = gmpy2.mpz(3)
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
print("p=%s,q=%s,e=%s"%(p,q,e))
print("d:%s"%d)

已知n,e,c求m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import gmpy2
import binascii

n = 966808932627497190635859236054960349099463975227350564265384373280336699853387254070662881265937565163000758606154308757944030571837175048514574473061401566330836334647176655282619268592560172726526643074499534129878217409046045533656897050117438496357231575999185527675071002803951800635220029015932007465117818739948903750200830856115668691007706836952244842719419452946259275251773298338162389930518838272704908887016474007051397194588396039111216708866214614779627566959335170676055025850932631053641576566165694121420546081043285806783239296799795655191121966377590175780618944910532816988143056757054052679968538901460893571204904394975714081055455240523895653305315517745729334114549756695334171142876080477105070409544777981602152762154610738540163796164295222810243309051503090866674634440359226192530724635477051576515179864461174911975667162597286769079380660782647952944808596310476973939156187472076952935728249061137481887589103973591082872988641958270285169650803792395556363304056290077801453980822097583574309682935697260204862756923865556397686696854239564541407185709940107806536773160263764483443859425726953142964148216209968437587044617613518058779287167853349364533716458676066734216877566181514607693882375533

p = gmpy2.mpz(31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928797450473)
q = gmpy2.mpz(31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928997877221)
e = gmpy2.mpz(65537)
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e, phi_n)
c = gmpy2.mpz(168502910088858295634315070244377409556567637139736308082186369003227771936407321783557795624279162162305200436446903976385948677897665466290852769877562167487142385308027341639816401055081820497002018908896202860342391029082581621987305533097386652183849657065952062433988387640990383623264405525144003500286531262674315900537001845043225363148359766771033899680111076181672797077410584747509581932045540801777738548872747597899965366950827505529432483779821158152928899947837196391555666165486441878183288008753561108995715961920472927844877569855940505148843530998878113722830427807926679324241141182238903567682042410145345551889442158895157875798990903715105782682083886461661307063583447696168828687126956147955886493383805513557604179029050981678755054945607866353195793654108403939242723861651919152369923904002966873994811826391080318146260416978499377182540684409790357257490816203138499369634490897553227763563553981246891677613446390134477832143175248992161641698011195968792105201847976082322786623390242470226740685822218140263182024226228692159380557661591633072091945077334191987860262448385123599459647228562137369178069072804498049463136233856337817385977990145571042231795332995523988174895432819872832170029690848)

m = pow(c, d, n)
print("十进制:\n%s"%m)
m_hex = hex(m)[2:]
print("十六进制:\n%s"%(m_hex,))
print("ascII:\n%s"%((binascii.b2a_hex(hex(m)[2:])).decode('hex'),))
print("ascii:\n%s"%(binascii.a2b_hex(m_hex).decode("utf8"),))

已知n,求p,q

使用yafu,下载地址:https://sourceforge.net/projects/yafu/
分解23333333333333

也可以在线分解 http://factordb.com/index.php

共模攻击

已知n,e1,e2,c1,c2,未知d1,d2,求m
假如采用两个公钥(N,e)来加密同一条信息,c1 = pow(m, e1, N),c2 = pow(m, e2, N),已知n,e1,e2,c1,c2,即可可以得到明文m,因为e1和e2互质,所以使用欧几里得算法(用于计算两个整数a,b的最大公约数),找到x,y满足pow(x,e1)+pow(y,e2)=1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from libnum import n2s, s2n
from gmpy2 import invert

# 扩展欧几里得算法
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)


def main():
n = 116547141139745534253172934123407786743246513874292261984447028928003798881819567221547298751255790928878194794155722543477883428672342894945552668904410126460402501558930911637857436926624838677630868157884406020858164140754510239986466552869866296144106255873879659676368694043769795604582888907403261286211
c1 = 78552378607874335972488545767374401332953345586323262531477516680347117293352843468592985447836452620945707838830990843415342047337735534418287912723395148814463617627398248738969202758950481027762126608368555442533803610260859075919831387641824493902538796161102236794716963153162784732179636344267189394853
c2 = 98790462909782651815146615208104450165337326951856608832305081731255876886710141821823912122797166057063387122774480296375186739026132806230834774921466445172852604926204802577270611302881214045975455878277660638731607530487289267225666045742782663867519468766276566912954519691795540730313772338991769270201
e1 = 1804229351
e2 = 17249876309
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
# 求模反元素
if s1 < 0:
s1 = - s1
c1 = invert(c1, n)
elif s2 < 0:
s2 = - s2
c2 = invert(c2, n)

m = pow(c1, s1, n) * pow(c2, s2, n) % n
print(n2s(m)) # 二进制转string


if __name__ == '__main__':
main()

已知n1,n2,求最大公约数p

已知n1,n2,求出一个公约数p,即为n1,n2共有的共因素p,在借助公式n=p * q 解出 q

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n1=9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
n2=13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743
a=int(n1)
b=int(n2)
def gys1(a,b): #辗转相除法(欧几里德算法)
if a<b:
a,b=b,a
while b!=0:
temp=a%b
a=b
b=temp
return a
def gys2(a,b): #更相减损法
while a!=b:
if a<b:
a,b=b,a
temp=a-b
a=temp
return a
print gys2(a,b)

已知n,e,c,dp,求m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2 
import libnum
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
for i in range(1,65538):
if (dp*e-1)%i == 0:
if n%(((dp*e-1)/i)+1)==0
p=((dp*e-1)/i)+1
q=n/(((dp*e-1)/i)+1)
  phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)%phi  
print libnum.n2s(pow(c,d,n))

已知dp,dq,q,p,c,求m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
import libnum
def decrypt(dp,dq,p,q,c):
InvQ = gmpy2.invert(q, p)
mp = pow(c, dp, p)
mq = pow(c, dq, q)
m = (((mp-mq)*InvQ) % p)*q+mq
print libnum.n2s(m)
dp=24417628139330679432551095868116968814142396193102639509841676574931690513464588523684381397207121003439385360929299071710433231196678202942915347185802024747158497456267595000613289619481116892073493417896024118597833611923086327107489774162727006791982668721110819684552525393969199138125692085053266311867
dq=39019112110614280252241495036646034807151213716557526376274345944263453299622818575225245299195523420254672088668617876062998490653404750105272510633841394184860866942704080992475543547501372565259180366123356119418623253283732615682878021900318153700726522250094020806743598752556541454865233668070931534349
p=114461439704891616590422134857421869878753559940962522699708885701308630438427731936479777010552391068812199529467348873013239528376604282404207321401876195560830474695517139918118078685078197948576662138382523308600480733574419071424466292785993331731881271557573094521160051353184489095799816579282742140953
q=173407999660109485520889209734134041910836523881475540116955713891631837403964097088089751678165465931150331234455699896350201315926126639981461748491240790317968076899655657331112140939100897570439934688992874242416328330344836429844042122956843979375681077968897817612357468397424082494911472122421034561779
c=13156088528156801357013836665002509320288819562687150049688430847488062217199478847649128772442129783962344653461951822569890099822350753026372449754819799394899656016487248023042927376134885257136511477879900672582593964626335310995748816166750941755394630154620318544805488209700324391789948495807096701620546557726907853315159542234979480907794659188799145765761654813882682456135251746607111274015475601810166327843158879230660349983897375641623569327757258851636029354634714133778666281729500815659100876558161468140039778498553902396380237570072543395294246750182054410091138654202418836971487515663618000662737
decrypt(dp,dq,p,q,c)

e=1

当e=1时,c = pow(m, e, n) = pow (m, 1, n) = m mod n,即 m = c + n * k (k=0,1,2,3,4…)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import binascii
import gmpy2
N_hex=0x180be86dc898a3c3a710e52b31de460f8f350610bf63e6b2203c08fddad44601d96eb454a34dab7684589bc32b19eb27cffff8c07179e349ddb62898ae896f8c681796052ae1598bd41f35491175c9b60ae2260d0d4ebac05b4b6f2677a7609c2fe6194fe7b63841cec632e3a2f55d0cb09df08eacea34394ad473577dea5131552b0b30efac31c59087bfe603d2b13bed7d14967bfd489157aa01b14b4e1bd08d9b92ec0c319aeb8fedd535c56770aac95247d116d59cae2f99c3b51f43093fd39c10f93830c1ece75ee37e5fcdc5b174052eccadcadeda2f1b3a4a87184041d5c1a6a0b2eeaa3c3a1227bc27e130e67ac397b375ffe7c873e9b1c649812edcd
e_hex=0x1
c_hex=0x4963654354467b66616c6c735f61706172745f736f5f656173696c795f616e645f7265617373656d626c65645f736f5f63727564656c797d

c_hex = gmpy2.mpz(c_hex)
N_hex = gmpy2.mpz(N_hex)

i = 0
while i<10:
m_hex = hex(c_hex + gmpy2.mpz(hex(i))*N_hex)
print(m_hex[2:])
try:
print(binascii.a2b_hex(m_hex[2:]).decode("utf8"))
except binascii.Error as e:
print("wrong")
i += 1

当c小于n时,c就是m

比如N=0x180be86dc898a3c3a710e52b31de460f8f350610bf63e6b2203c08fddad44601d96eb454a34dab7684589bc32b19eb27cffff8c07179e349ddb62898ae896f8c681796052ae1598bd41f35491175c9b60ae2260d0d4ebac05b4b6f2677a7609c2fe6194fe7b63841cec632e3a2f55d0cb09df08eacea34394ad473577dea5131552b0b30efac31c59087bfe603d2b13bed7d14967bfd489157aa01b14b4e1bd08d9b92ec0c319aeb8fedd535c56770aac95247d116d59cae2f99c3b51f43093fd39c10f93830c1ece75ee37e5fcdc5b174052eccadcadeda2f1b3a4a87184041d5c1a6a0b2eeaa3c3a1227bc27e130e67ac397b375ffe7c873e9b1c649812edcd
e=0x1
c=0x4963654354467b66616c6c735f61706172745f736f5f656173696c795f616e645f7265617373656d626c65645f736f5f63727564656c797d

只用 print libnum.n2s(c) 就行了

1
2
3
4
5
import libnum
n=0x180be86dc898a3c3a710e52b31de460f8f350610bf63e6b2203c08fddad44601d96eb454a34dab7684589bc32b19eb27cffff8c07179e349ddb62898ae896f8c681796052ae1598bd41f35491175c9b60ae2260d0d4ebac05b4b6f2677a7609c2fe6194fe7b63841cec632e3a2f55d0cb09df08eacea34394ad473577dea5131552b0b30efac31c59087bfe603d2b13bed7d14967bfd489157aa01b14b4e1bd08d9b92ec0c319aeb8fedd535c56770aac95247d116d59cae2f99c3b51f43093fd39c10f93830c1ece75ee37e5fcdc5b174052eccadcadeda2f1b3a4a87184041d5c1a6a0b2eeaa3c3a1227bc27e130e67ac397b375ffe7c873e9b1c649812edcd
e=0x1
c=0x4963654354467b66616c6c735f61706172745f736f5f656173696c795f616e645f7265617373656d626c65645f736f5f63727564656c797d
print libnum.n2s(c)

e=2

条件:e=2,n已知,因为不互素,所以无法求逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import gmpy2
import string
from Crypto.PublicKey import RSA

# 读取公钥参数
with open('lujing', 'r') as f:
key = RSA.importKey(f)
N = key.n
e = key.e

p = ...
q = ...
with open('./tmp/flag.enc', 'r') as f:
cipher = f.read().encode('hex')
cipher = string.atoi(cipher, base=16)
# print cipher

# 计算yp和yq
yp = gmpy2.invert(p,q)
yq = gmpy2.invert(q,p)

# 计算mp和mq
mp = pow(cipher, (p + 1) / 4, p)
mq = pow(cipher, (q + 1) / 4, q)

# 计算a,b,c,d
a = (yp * p * mq + yq * q * mp) % N
b = N - int(a)
c = (yp * p * mq - yq * q * mp) % N
d = N - int(c)

for i in (a,b,c,d):
s = '%x' % i
if len(s) % 2 != 0:
s = '0' + s
print s.decode('hex')

e=3

e-3时,爆破k,开e次方即可得到m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import libnum
from Crypto.Util import number
import gmpy2
def getd(e,p,q):
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi) % phi
return d
def getm(m):
return int(m.encode('hex'), 16)
c=...
n=...
e=3
i = 0
while 1:
if (gmpy.root(c + i * n, 3)[1] == 1):
m = gmpy.root(c + i * n, 3)[0]
print libnum.n2s(m)
break
i = i + 1

工具

rsatool

相关文章
评论
分享
  • base家族C语言实现

    base家族怕了怕了…. 基本原理https://bbs.pediy.com/thread-251117.htmhttps://bbs.pediy.com/thread-251248.htm base64加密: 1234567891...

    base家族C语言实现
  • RC4

    在密码学中,RC4(来自Rivest Cipher 4的缩写)是一种流加密算法,密钥长度可变。它加解密使用相同的密钥,因此也属于对称加密算法。RC4是有线等效加密(WEP)中采用的加密算法,是TLS可采用算法之一。 原理初始化秘钥...

    RC4
  • 一个有趣的a+b

    凯撒加密🤪 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859...

    一个有趣的a+b
Please check the parameter of comment in config.yml of hexo-theme-Annie!