202205_宁波市赛_Cr4ck2

Tags:共模攻击

0x00. 题目

n = 14571489544273684681632745165173941757355029852967262639728000988042839386897493030097099884895386115482493694058873038502860513888769546717076461092157274631880422404640774568976816310850151976919429837061384758878560393916832880369835035094654445542998583110983141044252629041042005200028747437532412882541760701913277010315019696176276304794162940731256361777150089869864848752521412637555443729084762017260965056626550279092491606837302796652497491465469860146607791410672793656097187677222298486237121302232907875363012059539134811841994652897489100941594071086553725267695160318463265760189436211892048571831049
e1 = 18181
e2 = 19937
c1 = 14086932244393217502907224674408736488830849146214227184918262698062675736724337554446711585503734671616977407523947180439538475650652413419679106435434870038055027980301567294772290568083578726775663339768961737480740922223388718943787094330870471886171540256870630059797491648906275021947443613254535459415614412289718705188895798826235866579862681303315446414825328707142227744471707921742768342732559562524019443552187374960675403256064296192626351031408014769594350992074453942709110651276633951009115468620886310509692671361261934324842739148921650085982490562922669906835464674323688759465709626540284576889210
c2 = 9788755099571270122752620318833990768386552453915390611782202313009843880011885989102462216813557305415919308702993594866012255516635580308442538867800280824955615413443022611149710694144180395588528536827198061901961298781041399064307258829088210698947995786806886824892341393690873854230422832064661235313593912677068722144241580197984421905987499008664508485233509643273752098892825326153287135195132848517181638343515469682704077797334084053581822968060796475866168907228760199308163970477417979781603099935953389513751241815586854968725454388470460653618696872424888914546835979441528674579794525553550639554293

0x01. WP

对同一个明文通过同一模数n使用不同的e加密得到不同的c，符合共模攻击的条件

共模攻击(mn相同ec不同)
当n不变的情况下，知道n,e1,e2,c1,c2可以在不知道d1,d2的情况下解出m。
首先假设e1e2互质，即gcd(e1,e2)=1
此时则有e1s1+e2s2=1
式中s1s2皆为正数，但是一正一负。
通过扩展欧几里得算法，我们可以得到该式子的一组解(s1,s2)，假设s1为正数，s2为负数。
因为$$c1=m^{e1}\ mod \ n,c2=m^{e2}\ mod \ n$$
所以$$(c1^{s1} \ c2^{s2}) \ mod \ n = ((m^{e1} \ mod \ n)^{s1} (m^{e2} \ mod \ n)^{s2}) \ mod \ n$$
根据模运算性质可化简为$$({c1}^{s1} \ {c2}^{s2}) \ mod \ n = (( m^{e1} )^{s1} ( m^{e2} )^{s2}) \ mod \ n$$.
即$$( c1^{s1} c2^{s2} ) \ mod \ n = ( m^{e1s1+e2s2} ) \ mod \ n$$
又前面提到的e1s1+e2s2=1
所以$$( c1^{s1} c2^{s2} ) \ mod \ n = m \ mod \ n$$
即$$( c1^{s1} c2^{s2} ) = m$$

exp.py

n = 14571489544273684681632745165173941757355029852967262639728000988042839386897493030097099884895386115482493694058873038502860513888769546717076461092157274631880422404640774568976816310850151976919429837061384758878560393916832880369835035094654445542998583110983141044252629041042005200028747437532412882541760701913277010315019696176276304794162940731256361777150089869864848752521412637555443729084762017260965056626550279092491606837302796652497491465469860146607791410672793656097187677222298486237121302232907875363012059539134811841994652897489100941594071086553725267695160318463265760189436211892048571831049
e1 = 18181
e2 = 19937
c1 = 14086932244393217502907224674408736488830849146214227184918262698062675736724337554446711585503734671616977407523947180439538475650652413419679106435434870038055027980301567294772290568083578726775663339768961737480740922223388718943787094330870471886171540256870630059797491648906275021947443613254535459415614412289718705188895798826235866579862681303315446414825328707142227744471707921742768342732559562524019443552187374960675403256064296192626351031408014769594350992074453942709110651276633951009115468620886310509692671361261934324842739148921650085982490562922669906835464674323688759465709626540284576889210
c2 = 9788755099571270122752620318833990768386552453915390611782202313009843880011885989102462216813557305415919308702993594866012255516635580308442538867800280824955615413443022611149710694144180395588528536827198061901961298781041399064307258829088210698947995786806886824892341393690873854230422832064661235313593912677068722144241580197984421905987499008664508485233509643273752098892825326153287135195132848517181638343515469682704077797334084053581822968060796475866168907228760199308163970477417979781603099935953389513751241815586854968725454388470460653618696872424888914546835979441528674579794525553550639554293import gmpy2 as gpdef 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)s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
if s1 < 0:s1 = - s1c1 = gp.invert(c1, n)
elif s2 < 0:s2 = - s2c2 = gp.invert(c2, n)m = pow(c1, s1, n) * pow(c2, s2, n) % n
print(bytes.fromhex(hex(m)[2:]))
# b'flag{afe12ec-c1be-421f-c0fa-ea2f6ceb10a0}'

或直接使用工具