WDCTFfinal_RSA

0x01 前言

在比赛的时候想了很久，脑子秀逗了一直在往共模攻击的方向思考，赛后复现的时候发现解题的思路还是挺简单的

0x02 题目

#! /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')

0x03 解题思路

已知随机取了5个大素数，分别组合后形成了十个N，但是两个N之间会有公因数，由此产生了共模攻击的错误思路。
正确思路：\
m^e = k₁n₁n₂+ c₁ \
m^e = k₂n₁n₃ + c₂ \
将两式相减得\
c₁ - c₂ = n₁ (k₁n₂-k₂n₃)\
c₂ - c₃ = n₁ (k₂n₂-k₃n₄)\
由两式可求得公因数n1，同理可得公因数n2,但是同时需要注意的是求出的公因数可能并不是质数，如果不是质数还需要对其进行因式分解。

0x04 解题脚本

#! usr/bin/python2.7
#coding=utf-8
import binascii
import math
import gmpy2
from gmpy2 import is_prime
def gcd(a, b):
	if a < b:
		a, b = b, a
	while b != 0:
		temp = a % b
		a = b
		b = temp
	return a



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 modinv(a, m):
	g, x, y = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m


c1 = 26759289732065101373918487257022057317116378299403846182147590704852836106051452352215422056170369600262283299468573635191132829146735499590347361821045921013314835661782640744159371939744848758358950510481610877057029892426652336829688965508825506000701085559213156239983083734054744219436247192751623545026176457364532166038785522374218661106859907885720690766081826237228035852377757973158401593818938960949634735135659635049685703458235041192965974727988285198633926856887410537101425718717807622288557155697036270259747042943114384041575369516651276693358693907067776655055120194484919011847416846297343670686249
c2 = 15956336503988104899442139893031598446659974409113317055375220479692733643471346478300185526614481406707520520159428501258218132628773332679268087734822136119974972254392298547457194061195343279168317679528598659297119545851098147652525064172423502531156031461405022692004689385094809863473408534125863954574280929258518282901558121646603922309227419821117043891192995129059118240133297676101521261735351494687527868703032927812971572317272669598360907643925727109663145671585294041988396862823214834171806715219665593081498106680054444446645609774778590823593719767077018583167033432947952480724418168595474053382738
c3 = 23224147070685416168097675241784003570389095467262927471701727719405492214335835027923471254400080567020236382043953319136306910038956667229711467725231521382758321789598830942790252151102754762884364608586021951651975294132260627502635228600073229202923986610304045681693780319534473500799869359754329158209363419476823528824855174860444087634272208350089105776673601993173634659094359301711788353627288867809148786675466288204363648095860520055148274682268440335672252181452688232913093931184460513117364373248892943688528418212647257129916010501861965270640308170973193419304060083110958103790711597251688404470878
c4 = 14600839580517485574200231268500493664991791742746118327040362118764458442866051989772756516259273104254190056870450671170290226092128010643000518158769552771092182887149078409826551871350753661676512241322527890693729882502013064958594134324846030283831441015202676895296690713235728475568091728456224696405127670041464699859976866691872244934309560251435215744674000468834526267014926004872350709103336776119723242954093754206411162291733501549618159991743338301901085997722111691902146387633521516111649533132205995369869404408916248529415434875782424380772299040703024669300548346536240707775925358854066996947464
c5 = 6944349969445236266305486035956198765237362183617307898883632432975525472440756331675565166720241301699648577551168090442687892224412830073072672050933799937438138867032572448368800343231959913863740229984543825526843020676445939283437414733199106361199449079156057583338364574880451488318308356113750689982463071871844909052956837036167928879742050298612455257173120861286891664149562693638703988490005870331077921827772150533734266225740073018627787192225602688382373047131491564421062244579870594501635347767463346923334248699096663198982343463119899471840741811365121713420048041444784605216085582683783857132799
c6 = 8573871909845133663868578137533745451459854421699739321128242581791642147519435377619403231688772882850925072820353097013375667889638030319648227557923969641306582833749968405872564355998586329351209014961824379491430587544159526511066830141068387208474950024257964143426467932283636221786848353070691723977440684842375444426518694404093924950962185725919828590109837270399078018697568637835143728575930321979076810102168329824417125087713566714729428830616759295043568393050221239643426976858312458097505340211242196514705850374798530133847041004458702244564345233767738077507407482301148138987590399205008783457001
c7 = 18505992838042300421123457869248056629547720626407997536026161477196234666209325948307965898922695499105092283355656824432363788436766706834638490725454158184260897897818379804496442789819609724191977434671936533812362717644011375258540444965576901474649137250041865774431398073899519049061454898697369461987784516554921896760527937521954821654285620696178401635380086139012727262139864834285670999464479755158642493555130011399029070030130499128536071193000200027986621636258556719697583649847872513934428286172187221536532437922222186226605628475950958703916207740883491065754413526166277667400311971074851626689247



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

if (is_prime(q/2)):
    	print q
else:
	print 'QwQ'
	'''
q = q/2 
c = 26759289732065101373918487257022057317116378299403846182147590704852836106051452352215422056170369600262283299468573635191132829146735499590347361821045921013314835661782640744159371939744848758358950510481610877057029892426652336829688965508825506000701085559213156239983083734054744219436247192751623545026176457364532166038785522374218661106859907885720690766081826237228035852377757973158401593818938960949634735135659635049685703458235041192965974727988285198633926856887410537101425718717807622288557155697036270259747042943114384041575369516651276693358693907067776655055120194484919011847416846297343670686249
n = p*q	
d = modinv(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()

0x05 后记

运行脚本后，你就可以惊奇的发现，这题没有flag？！是的没错，zz主办方在出题人出完题后又运行了一次脚本，于是flag就没了，而现场没人提出来，那就是没人做到这个步骤了(:з」∠)