RSA_n未知

Author Avatar
Xzhah 5月 22, 2018
  • 在其它设备中阅读本文章

题目

1
2
3
4
5
6
7
8
9
10
11
12
#! /usr/bin/python2.7
from Crypto.Util.number import size,bytes_to_long,getStrongPrime
from itertools import combinations
msg = bytes_to_long("Your secret flag is : xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
e = 65537
pri = []
f = open('cipherx.txt', 'w')
for i in range(5):
    pri.append(getStrongPrime(1024,65537))
for k in combinations(pri, 2):
    n = k[0] * k[1]
    f.write(str(pow(msg, e, n)) + '\n')

思路

m^e = k1n1n2+ c1

m^e = k2n1n3 + c2

将两式相减得 c1 - c2 = n1 (k1n2-k2n3)

c2 - c3 = n1 (k2n2-k3n4)

由两式可求得公因数n1，同理可得公因数n2,但是同时需要注意的是求出的公因数可能并不是质数，如果不是质数还需要对其进行因式分解。

解题

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
#! usr/bin/python2.7
#coding=utf-8
import binascii
import math
import gmpy2
from gmpy2 import is_prime

c1 = 13455981172983326464102311937762831661788310626361076786164994487793945326981111197066703467784063584677545316464486222690177319997065759168374653040496712059568682406584202721616582863702654975066950060466986422582257001703187853927809075825528343329091775200012208860563692058684819775698290978617780577594014210672865880497874392738697086445744342656347507587613428993075257255547029724259635931665971785614738909042286207279739603543188892504358133043289264464915763121424437513688474543252743250750837754962444189265768058493217120380229238478428390747580847275659398491959011425398794606200760449574140326761335
c2 = 4888187708328317620094507614800274226981107085929590254185425273559042976171503907943793194842845890835133406885671925681517347731439124039971268535772441389943526257018243714512592593512323296725941627631582840937936230289732464068819395084847503736153991018426601148001171410680610396315398455868476519242523364370643315263903656899707643857165005292144961418736390628879183534554050946402008748537061851428674751948379857099827888766867529291843558247067650218013841320566949128247840292451599528568785840031947044173916230774125850838571273228740235067857273673072775479606479505558411747622879981674961795496398
c3 = 1246234818568605038771725387770032809896657624658751197487822667705150496788266236821445252745402061440344837126297118817722352360943422714353348519968257483217425318287123603122559539044278216514618542935008251728016376351207287908907419066172027356649934716661853550169371283110451199593919378518682893908073257597996213276417788967527409800490507319098619694553882580772197585922179030322385772341029003564359719244782484762058530989277184051441547024568631595655539528137422918541855814336215841836541683256179952847812650782272979437883178787135567291812430132598562391722110607279005808604132547633446702754242
c4 = 5945807707085423616106397090464145288661224101014907693104654596081518092031824289580553655597136400293583390581989219838293858796303129177903562794487009660324129992480484791256849653177916440709763357317237732026978876936371843211238777064330897077782446698577278202922221650609784909136488983753316374328060041688862833502261386605214386656750469198595184961624056503168436674528338454488445689162595307651649338939926811181397583426347049799471037024928424365956074689363634987714880064366326557578148205795406310315807810873199906864220949509516643869325208494504730147145059516579980994124490343208766447536810
c5 = 6187445948828077692015970911804646938282242052772994916845077569070730070453969382819385152870562813549652542234501650247554999118997287612656768657169917874500360552882579507148077964788035519927189184337650311696041346297615679489279371787315665879866086591715868260088943256008041145891355773432381271043597673424658569516927545882320343535771872720945022165744462740208023473214182506701311573606230422976998106293803156552098142853857635121713770388765373265153557740921629496699557717987765469270646934300913295007513219413849883613183601728166411181113787689840581266359785250985019212532583960800460788015491
c6 = 5212091418073782411520553214182135709421767268933861097557470068670598830761237108296366132955527825989098372862689616150847719971020880914262684813844505249039731390296288313064277036616294317850242554242344468349017823603991546642546139312359635120516022621977198868713265236780584328968456455227210401242292651898111573896055644196069499504205254423973191477361052269017513569237003435455766967610384127786317357129201800175882818678442257638418605140567086462026872695510406713566416179338847089594383139719544078973639147656333759205784973323451162915648440751084782358602950098354039646328692181357908591122714
c7 = 3655638351649160392053613377223998746456935081525685917833104279800461813163792301601632928836306436302774882558931553763046873854372645433876037722220899647761264466458772539363592772806366025160060082392022496959043608616479633871824843539139765269866557324139669669180299880464960812373747543711884223811204173243558307161330834607275612285093379360358536623915157494256701984991891771698584900549732277659667805289723868414345078895913383480318010760628083474820289670382156241646315278789987701943251698483519785588242374214684684812447667402223553085547756490931266818022366894997520489636576763520143455761239

p = gmpy2.gcd((c1-c2),(c1-c3))
q = gmpy2.gcd((c5-c6),(c5-c7))
 
if (is_prime(p)):
	print p
else:
	print 'QAQ'
if (is_prime(q)):
    	print q
else:
	print 'QwQ'

q = q
c = 13455981172983326464102311937762831661788310626361076786164994487793945326981111197066703467784063584677545316464486222690177319997065759168374653040496712059568682406584202721616582863702654975066950060466986422582257001703187853927809075825528343329091775200012208860563692058684819775698290978617780577594014210672865880497874392738697086445744342656347507587613428993075257255547029724259635931665971785614738909042286207279739603543188892504358133043289264464915763121424437513688474543252743250750837754962444189265768058493217120380229238478428390747580847275659398491959011425398794606200760449574140326761335
n = p*q	
d = gmpy2.invert(65537,(p-1)*(q-1))
#print p
m = hex(pow(c,d,n)).rstrip("L")
flag = m[2:]
if len(flag)%2:flag='0'+flag
print binascii.unhexlify(flag)
raw_input()