RSA密钥生成

RSA密钥生成包括以下步骤：

算法描述 变量表示
①选择两个大质数p和q p, q
②计算n=pq n
③欧拉公式φ(n)=(p-1)(q-1) φ(n) (也可以是r)
④选择一个整数e，使得1<e<φ(n)，且e和φ(n)互质 e
⑤计算e关于φ(n)的模逆元d，即ed≡1(mod φ(n)) d

此时就能得到公钥(e, n)，私钥(d, n)

助记法则

  1. m：Message 或 Plaintext，表示原始消息或明文。
  2. c：Ciphertext，表示加密后的消息或密文。
  3. e：Public Exponent 或 Encryption Exponent，表示公钥指数，用于加密过程。
  4. d：Private Exponent 或 Decryption Exponent，表示私钥指数，用于解密过程。
  5. n：Modulus，表示模数，由两个大素数 p 和 q 的乘积构成。
  6. p：Prime Number 1，表示第一个大素数。
  7. q：Prime Number 2，表示第二个大素数。
  8. φ(n)：Euler’s Totient Function 或 φ-function，表示欧拉函数，计算小于 n 且与 n 互质的正整数的个数。

RSA破解原理

RSA成立的条件依赖于如下等式:(其中三等号的意思是同余)

fef100b24d84f343284c26af0694186d

1
2
(明文**e)%n=密文,  (密文**d)%n=明文
(m**e)%n=c , (c**d)%n=m

由于e,r互质根据贝祖定理(若e,r互质则总存在整数d,y使得 $$e\cdot{d}+r\cdot{y}=1$$)

两边同时取模r得ed(mod r)=1(mod r)

也就是说ed%r=1%r (ed和1对于r同余 )

表示为ed≡1(mod r)即ed-1=k*1(k为倍数)

求d即求e关于r的乘法逆元

d = gmpy2.invert(e,r)

RSA解题思路

已知p,q

1
2
3
4
5
6
7
8
9
10
11
12
from gmpy2 import *
from Crypto.Util.number import * 
e = 65537
p = 104046835712664064779194734974271185635538927889880611929931939711001301561682270177931622974642789920918902563361293345434055764293612446888383912807143394009019803471816448923969637980671221111117965227402429634935481868701166522350570364727873283332371986860194245739423508566783663380619142431820861051179 
q = 140171048074107988605773731671018901813928130582422889797732071529733091703843710859282267763783461738242958098610949120354497987945911021170842457552182880133642711307227072133812253341129830416158450499258216967879857581565380890788395068130033931180395926482431150295880926480086317733457392573931410220501 
c = 4772758911204771028049020670778336799568778930072841084057809867608022732611295305096052430641881550781141776498904005589873830973301898523644744951545345404578466176725030290421649344936952480254902939417215148205735730754808467351639943474816280980230447097444682489223054499524197909719857300597157406075069204315022703894466226179507627070835428226086509767746759353822302809385047763292891543697277097068406512924796409393289982738071019047393972959228919115821862868057003145401072581115989680686073663259771587445250687060240991265143919857962047718344017741878925867800431556311785625469001771370852474292194 
n = p*q 
phi_n = (p-1)*(q-1)

d = gmpy2.invert(e,phi_n) #求摸逆元e*d===1(mod phi_n) >>>   (e*d)%phi_n=1
m = pow(c,d,n) #求明文m=c**d%n
print(long_to_bytes(m))

因数分解

已知e,n,c,但n较小

当n位数<512时可以通过工具进行因数分解

1
2
3
4
5
6
7
8
9
10
11
12
from gmpy2 import *
from Crypto.Util.number import * 
e = 65537
n = 1455925529734358105461406532259911790807347616464991065301847
c = 69380371057914246192606760686152233225659503366319332065009
//用RSA网站分解n得到p,q的值
p=1201147059438530786835365194567
q=1212112637077862917192191913841
r=(p-1)*(q-1)
d=inverse(e,r)
m=gmpy2.powmod(c,d,n)
print(long_to_bytes(m))

共享素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from gmpy2 import *
from Crypto.Util.number import * 
e=65537 
n1=97651955426214592033572365773920057508427271716707728935577093505679682172372037636450110482557482581706749399826008020235313113944314376784907620141813540662534339234459496768240479220230957160400392913463409022293150429520768318670419503933186212191126307407839258074528684084840185308927331947537145829447
n2=66614608752278705185634904394365361979042404918604096433974094458632279000060400427645038515243709686328401390645112697979593615158483692603354348148482259753616268091570444012203646513399123035447707361637792128736541860728977309005359893376233152775475579396612879271884234088653699303606533505374905232923
c1=63953261435394891069612549636244603374173902686957436699829372333004288757335171873681401446375646490812908682109590243996379898870002800896829966763855784343173371142195534847739577115446177220108666069599165923313053697108515804761639807236996792227009426406166247412285289649024825203381481266356972774150
c2=57194972314389051543512820205703581413440756041185322107796772858205215016985575901911128530044596380489776006585803175505500161134431388478575594371310142237309980755948653414728132043884818377338689153219237884062208507665330097950793748413372319469773142224317762978585059400442666153359320918649028613087

p=gmpy2.gcd(n1,n2)
if(p>1):print("共享素数")
	q1=n1//p
r1=(p-1)*(q1-1)
d=inverse(e,r1)
m=pow(c1,d,n1)
print(long_to_bytes(m))

共模攻击

一个n两个e，两个密文，然后e1与e2互质适用情况
明文m、模数n相同，公钥指数e、密文c不同，gcd(e1,e2)==1
对同一明文的多次加密使用相同的模数和不同的公钥指数可能导致共模攻击，题目内容及解题脚本如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
from Crypto.Util.number import * 
e1 = 797
n = 15944475431088053285580229796309956066521520107276817969079550919586650535459242543036143360865780730044733026945488511390818947440767542658956272380389388112372084760689777141392370253850735307578445988289714647332867935525010482197724228457592150184979819463711753058569520651205113690397003146105972408452854948512223702957303406577348717348753106868356995616116867724764276234391678899662774272419841876652126127684683752880568407605083606688884120054963974930757275913447908185712204577194274834368323239143008887554264746068337709465319106886618643849961551092377843184067217615903229068010117272834602469293571
c1 = 11157593264920825445770016357141996124368529899750745256684450189070288181107423044846165593218013465053839661401595417236657920874113839974471883493099846397002721270590059414981101686668721548330630468951353910564696445509556956955232059386625725883038103399028010566732074011325543650672982884236951904410141077728929261477083689095161596979213961494716637502980358298944316636829309169794324394742285175377601826473276006795072518510850734941703194417926566446980262512429590253643561098275852970461913026108090608491507300365391639081555316166526932233787566053827355349022396563769697278239577184503627244170930
e2 = 521
c2 = 6699274351853330023117840396450375948797682409595670560999898826038378040157859939888021861338431350172193961054314487476965030228381372659733197551597730394275360811462401853988404006922710039053586471244376282019487691307865741621991977539073601368892834227191286663809236586729196876277005838495318639365575638989137572792843310915220039476722684554553337116930323671829220528562573169295901496437858327730504992799753724465760161805820723578087668737581704682158991028502143744445435775458296907671407184921683317371216729214056381292474141668027801600327187443375858394577015394108813273774641427184411887546849
_, r, s = gmpy2.gcdext(e1, e2)//获得最大公因数
//该函数用于计算两个整数的扩展欧几里得算法（Extended Euclidean Algorithm）。扩展欧几里得算法不仅可以计算两个数的最大公约数（GCD），还可以找到满足以下等式的整数 r 和 s：
e1⋅r+e2⋅s=gcd(e1,e2)
m=pow(c1,r,n)*pow(c2,s,n)%n
print(long_to_bytes(m))

证明 m=pow(c1,r,n)*pow(c2,s,n)%n:

证:

c1=m**e1 mod n

c2=m**e2 mod n

我们需要找到 m 通过扩展欧几里得算法，我们有： e1⋅r+e2⋅s=1

因此： m=m*(e1⋅r*+e2⋅s) mod n

m=(m**e1r)⋅(m**e2s) mod n

m=c1** r⋅c2**s mod n

根据数论(a*b)mod c = ((a mod c) * (b mod c)) mod c得

m=((c1**r mod n) * (c2* *s mod n ) ) mod n

即为m=pow(c1,r,n)*pow(c2,s,n)%n,得证

Rabin加密(e=2)

1
2
e=2
c=9217979941366220275377875095861710925207028551771520610387238734819759256223080175603032167658086669886661302962985046348865181740591251321966682848536331583243529
1
2
3
4
5
6
7
import gmpy2
from Crypto.Util.number import * 
# 密文
c = 9217979941366220275377875095861710925207028551771520610387238734819759256223080175603032167658086669886661302962985046348865181740591251321966682848536331583243529
# 计算平方根直接得出明文
m = gmpy2.isqrt(c)
print(long_to_bytes(m))

低加密指数攻击(e=3)

适用情况：e较小，一般为3。

公钥e很小，明文m也不大的话，于是m^e=k*n+m中的的k值很小甚至为0，爆破k或直接开三次方即可。解题脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import * 
import gmpy2
import time
//已知n,e,c
n=0xB0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
e=3
res=0
c=int('85C0DE5F89E88720AFD485F91DED38E9EAEDA3A61DDEE7087BBD29920EE40B6D53565EDD1E418095586BD4F33015729D433AF413C660E4C0B164ED025F91216D904578F7F20C5FB1E09E71992198D8E8D7FBD917597AEE45EBF4CA80124CE9B47ED163F0B9D5716A9D6E1F5B8AE09B16CAE30BBD64A15E17CC39A90FB62536AD943CDDA9A4AAC5978E3C93502535D5353638BC708C9B59CC9DC7BCB1D873336CE081591522B1D48904463783DD6837B1C41B8011889648E0ACDFBD3EE259F717990828D16DB34EB982446216DB534DC06B9E7AAF90BCCB54A1CC77C2813BDFE9A1B5C2E958C3EA8CA103BA1A89036B7014BBC962EB7A8C910E095BB83791BD9FEEE0D8F6AF0C2E030CCCC6D8729743419BDEE0A1E45AB5E7324A344761C8CC8DB30961A971D566E49C4562924C3EE001EDECE3445CD28DBA264BA8A90C5E533542096C26AA7D874997A308025A5E95BFC6949EBD16CEA889D242AB2E2FF2446090D07666D7574946E391D3F153D50346BC75DA94634182DF80F7BA97B77AF8922F13E43B2DF788902A209B9E569DD3C6FAA4DD7B43899F59798845DF642EDEEF34A186949CBE83C099F085F87A299591E715CCB4FE74612B00AEBE25C114819CF887C256121915416ACBCB058937E3D39EB7EF7143E145131119DA9C3D9818599A0E5109727FB581BBC20EB3E6A25011B8E9034537C0E580A0EE8F1553805BE8',16)

for i in range(200000000):
    if gmpy2.iroot(c+n*i,3)[1]==True:
        res=gmpy2.iroot(c+n*i,3)[0]
        print(i,res)
        print(long_to_bytes(res))
        print(time.asctime())
        break
        
#爆破时间比较长,耐心等待
#PCTF{Sm4ll_3xpon3nt_i5_W3ak}

低加密指数广播攻击

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
37
38
39
from gmpy2 import *
from Crypto.Util.number import * 
e= 66
N1=119121769301518368845794718919671993654866733452500635654897878290134654053525326323431078337969969799019267359311630307693231652437019657271070808881061234914792573940209704431930893007130218784789129628118174107530365963924713378836917676748173639617016078698196855902649715186446119049632882034064426307961
c1=65809670364005660919487930275712763981462574482844456704463641508675030596875121266268442889621086029848274337434417261197718575526373292499067042264634379254464845434162152933896113724853720502244098952049664997504481260560197503615640455874926744252021208987009450769588765905545554721135156365408354127806
N2=61566186989108648087416300713362112278899764336693876058459160266013125711319287023130470479677492361897176386933378510296253217497637077073380801285351720869599526467374766145998153803504733849848604084634651491161784374455431755730479983664183758338753000194705214689982392319657046639209576835502147667037
c2=18115640205116501705317897825685529616909607082926385394483386354114757190297813816634024391310034998634363199107263855395213222666209246729706790489666870667858157971452889316287713441243954970519480288407304588221367033667123438099684005390552527841793685576357398155728428068684443438517466992583270786127
N3=49620601251587487125794843250068355033366769115263317289571926701388354523775712535979072271377271193974631440599171766325666313148513015791734100817069816300041692142266535982235676202572289636401488831577138246100726048967727040512044104774134629062544550558359813957976997743249501859251552702735064713687
c3=20364551273681999294192219339422116302034809693463183300482896653538283331993131969988691606265882556683096226676587592788170379969499383217301366185026531161375199684493173814963347571110673161762110717226798673655139195202698236793103775569353384039792555128423824292553968745259900764497340831105893270668
N4=133768952546673974479267370043541821144327252413845057783412528835180467846794140834703340900450314588506064435986442748604490312840370944318831808038247604353142259774616789531310532099928688408187901346284844605463451751550642385234492519392161741592575670083174919697609061113010796634206284575928757770347
c4=22335147582261003096647361522544076689364215203577454506488628401661580234233487251113839217854903668779299757152861854671534567147471797316820888992633912660481204658071146602886247900634407701930940651893906501617828267768494421662988585157809528901989990526581772462692969725469920335864514415298683981152
N5=104238024627494572746286964408730592545438306156311797513852804744729437956789203459026451862359528868190073408381414599237366462763241253878521105956224668414556141866393372950736873591172081402165238904932429122534093530878197642654777864463461868631230091763766134406081081720779921003747961997853491818709
c5=61107680391468684099981865276084215683172351113581670204727453862376840773256630839617142751881760857118348248250665317785917421351743397747894492411488165649401344879494773021769753591034395672465464320101652438687007539489378513821420800168510776217853333899011972317527520705236204176156830739081757405010
N6=118093066310605305095178937425517218630920226424744215661148532092308033934450073432943193635177662130252180103285721213804150321735225466812961622185616533145516398760950723892924696182721299397022483621950837139563238753686038378878896091768848068910135093028294780235384684673963857093300627549709837724191
c6=101256774269533055751457908208739377897424415487989206153587587300686603196557467291720330319232901633692785986681754036193235741811711502795701089320073392059949682466544065711958098750432374898558703333440618699807232864181819519679629167853668660602661341767124570492408045291007778414318130631983777295722
N7=117266185117654060034588324842366454222593927099393980357544774885629794379293166947229056918034459043108797074800162507024079391634502468534298624692449903107493118323020446890562744571191659344011645864382773946531469367984674369644899983010063210039853704185508764560001673741477659408982947064250518468251
c7=21894778019803458880260502198065610444404240072805403208023426906088005779594929836443213559388796713650945356366966043756862672829855657911990319072200008974506146871357573453019048449580079826767546217579688605917001867071164255859862228831932900353755873078336344643599953154397168889370495902677409294153
N8=99847214607089521961572435869957506429243606231877563380090692185420163672773289159042830799683260860597767443996073308175724597182454633588936213254523487111523733480984498586740358607988160025505687559762411862688601742397266945003398123269294496360100900034452611602146601714399455590585410132690396673369
c8=11128692723492689091233850419200963897271177985178577230436424149628046051146025178276383119267304777164785849951881090840591723497899208506838095610670693372018592133149773642812004657103063248374199581071604408292558846603838509738685590699272289726570262682986682351416702749398587242245473894462138900648
N9=73427226276805128656380869285386076721624609211443253475771428129504719457080180710705115744294619063551381264408504585408453508098823007044451551756211573562886310458270583742465979942941865777506724593733211095696183935690743247534548446509454942543803005250835909564142934138252786381937066184736196312879
c9=60193454951754852266094357956076086266071986040245653496529985198812436356863824995533097435342514985019627989807883105986263640682220256055428754363731882409970562687108383307540077970131766447280258179403586275956059172183226613848213900224857274285495001205557394336770529098104967590355473696826791159828
N10=99650442092528521150438911689808375993056822587606174829817567886601559468699368030195401941419824519727962816960977430480509904789178542213483386082107556343628416294902342864312889447653789084402767394237032107269596219826822529277688614898127656366069731819304375099356344677466185988432876228367727625953
c10=90419774897115225091366412014190084386457096921784011494379232133660413968111145130899089066669099521330755985696967486931277095415375171113368395860214365412786048972643171579220518548850903517117393998100848799427493429304884036350416671209777072844176863411890909720103357069783802064257545060602175751149
nlst=[N1,N2,N3,N4,N5,N6,N7,N8,N9,N10]
clst=[c1,c2,c3,c4,c5,c6,c7,c8,c9,c10]
N=1
for n in nlst:
    N*=n
mlst=[]
for n in nlst:
    mlst.append(N//n)
tlst=[]
for i in range(len(nlst)):
    tlst.append(inverse(mlst[i],nlst[i]))
sum=0
for i in range(len(nlst)):
    sum=(sum+clst[i]*tlst[i]*mlst[i])%N
m=gmpy2.iroot(sum,e)[0]
print(long_to_bytes(m))

Wiener攻击(连分数攻击)

1
2
3
from gmpy2 import *
from Crypto.Util.number import *

Roll按行加密

给了个文件{920139713,19}

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
37
38
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
e为19
因此解题脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
from Crypto.Util.number import long_to_bytes
n = 920139713
p = 49891
q = 18443
e = 19
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = ""
with open('roll.txt','r') as f:
    for c in f.readlines():
        m += long_to_bytes(pow(int(c), d, n))
print(m)