Press "Enter" to skip to content

[CodeBlue 2017] Common Modulus 2

Published November 10, 2017 by SaBeLa

Question

problem.py:

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
from Crypto.Util.number import *
from Crypto.Random.random import randint
 
import gmpy
import key
 
FLAG = long(key.FLAG.encode("hex"), 16)
 
def get_random_prime(bits=1024):
  return int(gmpy.next_prime(randint(2**(bits-1), 2**bits)))
 
def gen_n(bits=1024):
  p = getStrongPrime(bits)
  q = getStrongPrime(bits)
  return p*q, p, q
 
def encrypt(pk, m):
  assert m < pk[0]
  return pow(m, pk[1], pk[0])
 
def decrypt(pk, sk, c):
  return pow(c, sk[0], pk[0])
 
def test(n, p, q):
  e = 3 * get_random_prime(20)
  pk, sk = (n, e), (long(gmpy.invert(e, (p-1)*(q-1))), )
  print "[+] RSA Self Test: %r" % (pk, )
  c = encrypt(pk, FLAG)
  print "[+] ciphertext = %d" % c
  m = decrypt(pk, sk, c)
  print "[+] Dec(Enc(m)) == m? : %s" % (m == FLAG)
 
 
if __name__ == "__main__":
  n, p, q = gen_n(2048)
  test(n, p, q)
  test(n, p, q)

transcript.py:

1
2
3
4
5
6
7
8
[+] RSA Self Test: (691611766208546073444876122261067788277978858453710639029761974358666489171591889808344592871468081368348731289584873825685836699513369087940744233044470468106283756269016888690397802087612562650740690626844050981638158798650899164329024889012339813251634342169796374490173324858177655412520581064091323105709703802894635752243504165527728325493775585018099572491218738859140069209745383085972126419677929983854492018948495162457428459536088314487922683148031388611849013227501962458386817851194913551405843074740308192841259015955432216658418219471365781271743026881045054161177699500233983945284463060091084401032681620162554495490307966608011765399197534175588394769839991952726269105973546086964385977836193216093842605576347580465390858378577913173391209728199847916944392685608959720919745441534152140791433228642857247821519585327091864890122871765266988285510728943279970135846908966516130597249552710186071954611133294079017500030355232895541367427153922527925908108643934213023557398363684188823565535815365161748782796247844503993809352854741573950620787090272760236473228652960605730173150252619759400890068298838592790770868307280012495168740250977525199965477849089021924445456338550258621310346872587368865023459114279L, 2623119)
[+] ciphertext = 632613645684838434911920364870092246688638723680203743297038042884981435531349983627632652213126007404455112992754038899192740232209237012089852184466576496173356903126767617531366105427616049893559911396536574555008451239827427140619373005107923039458285095437111146013805698400274937791209388463040761234346114146112603113513874269976957472698342250573902102976387047390228485927254752372525379266486917620487089416581168720140744193600912161065888758451629009978676721731074043142666019127528370181044741033938879227651226413524178992155234346229899043794846119210274959231350300191718278291314079326011260972911790929707654859407903619102516710246683375658271085356783673232677699444921875427077745087507202504075374873842972977165904031632108921391219453633100007509368853543202918527396858214941532156620908283394786740941868393377733920317480973184132461984594109692489226477402338664642727766514992506288377119275635222078018270479534265371971469799345627297451492177595572561618185463142728664331779856911512823762928116551034186671353283417747535010208121962539603383913657773795358612010178381857101029638404248669376029927680328805839410427459248430136708902815920536603541943356116875656311481908672896225539754812052984
[+] Dec(Enc(m)) == m? : True
 
 
[+] RSA Self Test: (691611766208546073444876122261067788277978858453710639029761974358666489171591889808344592871468081368348731289584873825685836699513369087940744233044470468106283756269016888690397802087612562650740690626844050981638158798650899164329024889012339813251634342169796374490173324858177655412520581064091323105709703802894635752243504165527728325493775585018099572491218738859140069209745383085972126419677929983854492018948495162457428459536088314487922683148031388611849013227501962458386817851194913551405843074740308192841259015955432216658418219471365781271743026881045054161177699500233983945284463060091084401032681620162554495490307966608011765399197534175588394769839991952726269105973546086964385977836193216093842605576347580465390858378577913173391209728199847916944392685608959720919745441534152140791433228642857247821519585327091864890122871765266988285510728943279970135846908966516130597249552710186071954611133294079017500030355232895541367427153922527925908108643934213023557398363684188823565535815365161748782796247844503993809352854741573950620787090272760236473228652960605730173150252619759400890068298838592790770868307280012495168740250977525199965477849089021924445456338550258621310346872587368865023459114279L, 2611101)
[+] ciphertext = 473583830101449207063655453483957320801977763405664178108962387145963115641321631378723122470718049239150183483107837540062110255460217493574236417576528210993551734521104360323008425196350719034294427914294044848231276934402896045785500160974092767601908407706594433190832523140982335688121038712802163776950422665847149664034820576774873956120202470663588902529914328392634164212558025176982387474287314624421143326789371057668708456922968762564019631616913937820209470604081356673188045257490667304640155390478645279862586730343779998826931285683980941686981775369499484033439920659579124275957233449431588512697916708510428626881790592757578867152025501459202793986322020476004209777449674143157280081483085868896558215825742742029607229809248023263081810931655981810534293127835168642962477010095223356972141559004635008185531900175232541978761179342338914489553003329293031284557554252476291770973145365678145226167965362251186233138510776436645583796590010200995100899736056399413460647507781994189935869541735701599175369334170081795310585938471394672279359692859881857399434361716843681313191143289947464231132723256066979526475873327590657111481299295002695482778491520250596998683754980263059514032256777144682239680031331
[+] Dec(Enc(m)) == m? : True

 

Solution

Compare with v1, v2 just make changed in exponent. So, what we need to do is only find the root after get the result.

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
import sys
import gmpy2
 
sys.setrecursionlimit(100000);
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
def main():
 
  n= 691611766208546073444876122261067788277978858453710639029761974358666489171591889808344592871468081368348731289584873825685836699513369087940744233044470468106283756269016888690397802087612562650740690626844050981638158798650899164329024889012339813251634342169796374490173324858177655412520581064091323105709703802894635752243504165527728325493775585018099572491218738859140069209745383085972126419677929983854492018948495162457428459536088314487922683148031388611849013227501962458386817851194913551405843074740308192841259015955432216658418219471365781271743026881045054161177699500233983945284463060091084401032681620162554495490307966608011765399197534175588394769839991952726269105973546086964385977836193216093842605576347580465390858378577913173391209728199847916944392685608959720919745441534152140791433228642857247821519585327091864890122871765266988285510728943279970135846908966516130597249552710186071954611133294079017500030355232895541367427153922527925908108643934213023557398363684188823565535815365161748782796247844503993809352854741573950620787090272760236473228652960605730173150252619759400890068298838592790770868307280012495168740250977525199965477849089021924445456338550258621310346872587368865023459114279L
  e1= 2623119
  e2= 2611101
  c1= 632613645684838434911920364870092246688638723680203743297038042884981435531349983627632652213126007404455112992754038899192740232209237012089852184466576496173356903126767617531366105427616049893559911396536574555008451239827427140619373005107923039458285095437111146013805698400274937791209388463040761234346114146112603113513874269976957472698342250573902102976387047390228485927254752372525379266486917620487089416581168720140744193600912161065888758451629009978676721731074043142666019127528370181044741033938879227651226413524178992155234346229899043794846119210274959231350300191718278291314079326011260972911790929707654859407903619102516710246683375658271085356783673232677699444921875427077745087507202504075374873842972977165904031632108921391219453633100007509368853543202918527396858214941532156620908283394786740941868393377733920317480973184132461984594109692489226477402338664642727766514992506288377119275635222078018270479534265371971469799345627297451492177595572561618185463142728664331779856911512823762928116551034186671353283417747535010208121962539603383913657773795358612010178381857101029638404248669376029927680328805839410427459248430136708902815920536603541943356116875656311481908672896225539754812052984
  c2= 473583830101449207063655453483957320801977763405664178108962387145963115641321631378723122470718049239150183483107837540062110255460217493574236417576528210993551734521104360323008425196350719034294427914294044848231276934402896045785500160974092767601908407706594433190832523140982335688121038712802163776950422665847149664034820576774873956120202470663588902529914328392634164212558025176982387474287314624421143326789371057668708456922968762564019631616913937820209470604081356673188045257490667304640155390478645279862586730343779998826931285683980941686981775369499484033439920659579124275957233449431588512697916708510428626881790592757578867152025501459202793986322020476004209777449674143157280081483085868896558215825742742029607229809248023263081810931655981810534293127835168642962477010095223356972141559004635008185531900175232541978761179342338914489553003329293031284557554252476291770973145365678145226167965362251186233138510776436645583796590010200995100899736056399413460647507781994189935869541735701599175369334170081795310585938471394672279359692859881857399434361716843681313191143289947464231132723256066979526475873327590657111481299295002695482778491520250596998683754980263059514032256777144682239680031331
  s = egcd(e1, e2)
  s1 = s[1]
  s2 = s[2]
 
  if s1<0:
    s1 = - s1
    c1 = modinv(c1, n)
  elif s2<0:
    s2 = - s2
    c2 = modinv(c2, n)
  m = (pow(c1,s1,n)*pow(c2,s2,n))%n
  gmpy2.get_context().precision=2000
  m = gmpy2.root(m,3)
  print str(hex(int(str(m)[:-2])))[2:-1].decode('hex')
if __name__ == '__main__':
  main()

Share the post "[CodeBlue 2017] Common Modulus 2"

Comments

Published in CodeBlue 2017

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *