from random import randint from gmpy2 import * n = 0x4333AF6B43F36028D8D9650EC3EED3238541EE5C15E626C58C9EC33674A6D08D5B1F2580A1A0B07E9D853536CD994E197889D122701A62BB2A9E79559F3D5281014535F6C54F83CA8D9700EEB67D99AF318D20A5150AD46D622A6A12DE0A758EE7DF75F5D10F2FE2585F2348537787063321FFDAC91BB3C3D1D88CBD04A824ED x2 = 1 c = 7 while1: x1 = randint(1, n) x2 = pow(x2,2,n)+c%n fac = gcd(abs(x1-x2),n) if fac>1and is_prime(fac): print fac break print n/fac
Pollard rho p-1算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
from gmpy2 import * defPollardRho_p_1(N): a = i = 2 while1: a = pow(a, i, N) d = gcd(a - 1, N) if d != 1: return d break i += 1
n = 3233
res = PollardRho_p_1(n) print res print n/res
Fermat算法
适用于 p q 相差不大的时候
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
from gmpy2 import * defFermat(n): a = isqrt_rem(n)[0]+1 b = a ** 2 - n while1: q = isqrt_rem(b) if q[1] == 0: return a - q[0] a += 1 b = a ** 2 - n
n = 3233 res = Fermat(n) print res print n/res
公约数分解n
使用相同的p,分别得知n1和n2
1 2 3 4 5 6 7 8 9
import gmpy2 n1 = 9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327 n2 = 13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743 p = gmpy2.gcd(n1, n2) print'gcd(n1, n2):\n', p q1 = n1 / p q2 = n2 / p print'q1 is:\n', q1 print'q2 is:\n', q2
# -*- coding: cp936 -*- import gmpy2 e = 3 # 读入 n, 密文 c n= 22885480907469109159947272333565375109310485067211461543881386718201442106967914852474989176175269612229966461160065872310916096148216253429849921988412342732706875998100337754561586600637594798877898552625378551427864501926224989873772743227733285336042475675299391051376624685754547818835551263597996620383338263448888107691240136257201191331617560711786674975909597833383395574686942099700631002290836152972352041024137872983284691831292216787307841877839674258086005814225532597955826353796634417780156185485054141684249037538570742860026295194559710972266059844824388916869414355952432189722465103299013237588737 c= 15685364647213619014219110070569189770745535885901269792039052046431067708991036961644224230125219358149236447900927116989931929305133870392430610563331490276096858863490412102016758082433435355613099047001069687409209484751075897343335693872741 print'[+]Detecting m...' result = gmpy2.iroot(c, 3) print' [-]The c has cubic root?', result[1] if result[1]: print' [-]The m is:', '{:x}'.format(result[0]).decode('hex') print'[!]All Done!'
e=3 时的小明文攻击(e = 3 且明文的三次方比 n 大,但是不是足够大)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
# -*- coding:utf-8 -*- import gmpy2, time e = 3 # 读入 n, 密文 n = 114976915747243387792157708464120735018971336213935438953074748276198282761939060395482051056351068439137722626185590043024556656813730840050547350912425438364703854627760482842307943026011880815011654341047422453012558617703411700393668892701036222135444420377515575624398723436532681305293727164639582093389 c = 5828813410620741112500628876643872258919868379601617907887884191584237969605489971465692568848339200057188383649365078832766143513766368216471491824042974016773526107276856706832404477882581400769791378958901067683158857990261489285951805740071223765359992165262854641069674603160977034446644199945940251030 i = 239000000# i 应该是未知的。这里缩短一下距离, 防止跑得太久 print'[+]Detecting m...' s = time.clock() while1: m, b = gmpy2.iroot(c + i * n, 3) if b: print' [-]m is: ' + '{:x}'.format(int(m)).decode('hex') break #print ' [-]i = %d\r' % i, i += 1 print'[!]Timer:', round(time.clock() - s, 2), 's'
# -*- coding: cp936 -*- import gmpy2 import time defCRT(items): N = reduce(lambda x, y: x * y, (i[1] for i in items)) result = 0 for a, n in items: m = N / n d, r, s = gmpy2.gcdext(n, m) if d != 1: raise Exception("Input not pairwise co-prime") result += a * s * m return result % N, N # 读入 e, n, c e = 9 n = [142782424368849674771976671955176187834932417027468006479038058385550042422280158726561712259205616626939123504489410624745195777853423961104590708231562726165590769610040722589287393102301338152085670464005026301781192671834390892019478189768725018303217559795377795540494239283891894830166363576205812991157L, 153610425077816156109768509904751446801233412970601397035720458311275245730833227428213917577405780162151444202393431444812010569489900435979730559895340377469612234558042643742219128033827948585534761030527275423811282367831985007507137144308704413007806012914286105842311420933479771294576841956749281552971L, 152540067782701001222493009941492423063369171831039847414320547494725020441901272486665728360741395415762864872737675660423920609681185809510355937534756399208661762715484879562585724584849261266873624875852300611683382543315580370484972470694466195837255994159609193239840228218925381488410059939975556977947L, 125842716702134814646356078531900645012495638692517778270527426844383063904041812273637776798591687732598509470005151551320457132061693618473039437320011446697406190781306264437609046721508738109650829547010385875425097336266103994639126319889016342284747700714199556143378526590058467791687837422897022829661L, 116144389285266462769913139639175922392318396923181100785008570884082681963637784423143843845816350379438789947802939701820129805341796427821894273985551331666719808355412080909245720551238149511778060242720419584504473490216670437024863860559347959698828131475160058721701582089480924088773887932997353631767L, 127833907448946785858374094953899556339175475846831397383049660262333005992005484987913355932559627279178940862787593749842796469355336182379062826441222705075178971785791223706944120681105575965622931327112817747065200324610697178273898956820957640413744954233327851461318200323486469677469950386824833536523L, 130561613227079478921314550968562766645507834694262831586725464124109153306162445639759476845681271537955934718244296904503168256991962908095007040044300188572466395275317838178325500238288302672390013747102961340256309124310478931896245221622317302428447389760864327859640573452084295225059466376349115703119L, 115953389401040751013569404909249958538962411171147823610874077094621794755967854844224923689925397631692572916641171075740839099217316101334941033937183815345038898177087515909675028366437302462022970987947264115373697445950951595479758872029099661065186221250394358255523574834723958546450323357472451930993L, 143437107845384843564651522639125300763388830136500260725097766445883003928355325003575359566631064630487365774344508496878731109174874449170057678821440711511966073934025028100604234445470976333825866939923998344367645612128590820812489407412175198698290167077116185959180877334222693344630253253476594907313L] c = [85033868418784308573673709960700777350314426427677627319697346811123742342359072170220428874952996988431950989321281905284522596263957356289624365171732095210045916218066135140320107686084053271623461104022705353814233772164502775939590711842361956121603943483040254727995655776263673058788416722141673409688L, 66065963470666895005407449599703926269325406456711861190876894466341571726360462706664546294453572319565476664348345756905411939632955966517708138047546806602828064213238537646393524578984547577761559965654539771172357089802682793169968961304179886652390277814477825753096636750388350662980872556701402397564L, 116011740820520887443111656288411611070614127688662643257265381793048354928820176624229624692124188995846076431510548507016903260774215950803926107831505634778278712070141663189086436127990584944132764896694777031370995058271038329228336417590284517922855284619653301817355115583540545182119702335431334401666L, 97640420284096094887471273365295984332267897927392169402918423863919914002451127544715668846623138003564829254309568918651163254043205129883843425179687841236818720463784828905460885026290909768599562386370732119591181513319548915478512030197629196018254041500662654260834562708620760373487652389789200792120L, 8112507653841374573057048967617108909055624101437903775740427861003476480616929517639719198652146909660899632120639789106782550275648578142883715280547602249589837441805676364041484345030575130408744621981440093280624046635769338568542048839419939250444929802135605724150484414516536378791500915047844188300L, 36792148360808115566234645242678223867680969786675055638670907933041180936164293809961667801099516457636164692292891528415720085345494773373966277807505798679784807614784581861287048096977968620964436947452527540958289441390882589051225367658014709290392321808926567572528170531844664734909469690750971883323L, 53043093283305492238903255767698153246673671181809989362223466090875767705978690531154079519999671834688647277179370374802495005937892824566602423646978168777735383632928274082669949750078161820002768640908750005814934158829006019656592134357897586040866207754535586785064545866404380204728594863102313407789L, 88499407133762624445946519155722583633934260410706930537441122463087556094734626189377091740335667052378955691250910459790202385799502439716173363179773811920751410726795431402796346647688144853156900427797933862087074385441977254140336390678022955770879265490567987868532251217565094093318626424653599450992L, 138337520305048557335599940473834485492131424901034295018189264168040969172072024612859307499682986987325414798210700710891033749119834960687318156171051379643844580970963540418974136891389303624057726575516576726845229494107327508855516437230240365759885913142671816868762838801720492804671259709458388192984L] print'[+]Detecting m...' data = zip(c, n) x, n = CRT(data) realnum = gmpy2.iroot(gmpy2.mpz(x), e)[0].digits() print' [-]m is: ' + '{:x}'.format(int(realnum)).decode('hex') print'[!]All Done!'
Coppersmith 定理攻击
如果 e = 3 并且在明文当中只有三分之二的比特是已知的,这种算法可以求出明文中所有的比特。
暂未有python脚本,需要依靠sage运行。
sage在线运行:
1
https://sagecell.sagemath.org/
共模攻击
如果在 RSA 的使用中使用了相同的模 n 对相同的明文 m 进行了加密,那么就可以在不分解 n 的情况下还原出明文 m 的值。例子:
n = 135176830582884945708175419898330054260341730432046991449072509302750602166218145078102928897914789996197402658592881347572949256377161172079344803330624352445165759925647345536051853372740246104804540179716136644319380454884518397455488002758429914465640804944658049262500561494830899678619427468784748988379
defisCoPrime(x,y): ma = 0 mi = 0 ma=max(x,y) mi=min(x,y) if x==1or y==1: returnTrue if x % y == 0: print x print y returnFalse return isCoPrime(mi,ma % mi)
from Crypto.Util.number import getPrime, bytes_to_long, inverse from secret import flag
assert(len(flag) < 87) # leave space for padding since padding is secure
p = getPrime(1024) q = getPrime(1024) n = p*q e = 3 d = inverse(e,(p-1)*(q-1)) m = bytes_to_long(flag.center(255,"\x00")) # pad on both sides for extra security c = pow(m,e,n) print("n = {}".format(n)) print("e = {}".format(e)) print("c = {}".format(c))
1 2 3
n = 16930533490098193592341875268338741038205464836112117606904075086009220456281348541825239348922340771982668304609839919714900815429989903238980995651506801223966153299092163805895061846586943843402382398048697158458017696120659704031304155071717980681280735059759239823752407134078600922884956042774012460082427687595370305553669279649079979451317522908818275946004224509637278839696644435502488800296253302309479834551923862247827826150368412526870932677430329200284984145938907415715817446807045958350179492654072137889859861558737138356897740471740801040559205563042789209526133114839452676031855075611266153108409 e = 3 c = 11517346521350511968078082236628354270939363562359338628104189053516869171468429130280219507678669249746227256625771360798579618712012428887882896227522052222656646536694635021145269394726332158046739239080891813226092060005024523599517854343024406506186025829868533799026231811239816891319566880015622494533461653189752596749235331065273556793035000698955959016688177480102004337980417906733597189524580640648702223430440368954613314994218791688337730722144627325417358973332458080507250983131615055175113690064940592354460257487958530863702022217749857014952140922260404696268641696045086730674980684704510707326989
from Crypto.Util.number import inverse, bytes_to_long, long_to_bytes from binascii import * from sympy import integer_nthroot n = 16930533490098193592341875268338741038205464836112117606904075086009220456281348541825239348922340771982668304609839919714900815429989903238980995651506801223966153299092163805895061846586943843402382398048697158458017696120659704031304155071717980681280735059759239823752407134078600922884956042774012460082427687595370305553669279649079979451317522908818275946004224509637278839696644435502488800296253302309479834551923862247827826150368412526870932677430329200284984145938907415715817446807045958350179492654072137889859861558737138356897740471740801040559205563042789209526133114839452676031855075611266153108409 e = 3 c = 11517346521350511968078082236628354270939363562359338628104189053516869171468429130280219507678669249746227256625771360798579618712012428887882896227522052222656646536694635021145269394726332158046739239080891813226092060005024523599517854343024406506186025829868533799026231811239816891319566880015622494533461653189752596749235331065273556793035000698955959016688177480102004337980417906733597189524580640648702223430440368954613314994218791688337730722144627325417358973332458080507250983131615055175113690064940592354460257487958530863702022217749857014952140922260404696268641696045086730674980684704510707326989 seen = [] for l in range(87): print(l) lp = (255-l)//2 if lp in seen: continue else: seen.append(lp)
A = 2**(8*lp*e) Ainv = inverse(A,n) cu = (c*Ainv)%n bam = 24*l - 2048 + 1 bam = bam+1if bam>0else1 for j in range(2**bam): m = integer_nthroot(cu+j*n,3)[0] m = long_to_bytes(m) ifb'actf'in m: print(m) break
求解明文
已知p,q,e,c:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
import gmpy2
p = gmpy2.mpz(9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483) q = gmpy2.mpz(11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407) e = gmpy2.mpz(65537) phi_n = (p - 1) * (q - 1) d = gmpy2.invert(e, phi_n) print"private key:" print d
c = gmpy2.mpz(83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034) print"plaintext:" print pow(c,d,p*q)
1 2 3 4 5 6 7 8 9 10 11
#!/usr/bin/env python3 import gmpy2 p = gmpy2.mpz(18443) q = gmpy2.mpz(49891) L = (p-1)*(q-1) e = 19 with open('rsaroll.txt') as File_project: for line in File_project: c = int(line.strip()) d = gmpy2.invert(e,L) print(pow(c,d,p*q),end=' ')