Find short vectors in two-dimensional lattices

Contents

Notes for $An\ Introduction\ to\ Mathematical\ Cryptography$

“A toy model of a real public key cryptosystem”

  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  from Crypto.Util.number import bytes_to_long, getPrime, inverse from gmpy2 import iroot q = getPrime(1024) f = getPrime(511) g = getPrime(511) while g < iroot(q//4, 2)[0] or g > iroot(q//2, 2)[0]: g = getPrime(511) f_inv_q = inverse(f, q) h = f_inv_q*g % q m = bytes_to_long(b'flag') # flag is base**(flag) r = getPrime(510) e = (r*h+m) % q print(f) print(g) print(q) print(e) ''' f = 4685394431238242086047454699939574117865082734421802876855769683954689809016908045500281898911462887906190042764753834184270447603004244910544167081517863 g = 5326402554595682620065287001809742915798424911036766723537742672943459577709829465021452623299712724999868094408519004699993233519540500859134358256211397 q = 172620634756442326936446284386446310176482010539257694929884002472846127607264743380697653537447369089693337723649017402105400257863085638725058903969478143249108126132543502414741890867122949021941524916405444824353100158506448429871964258931750339247018885114052623963451658829116065142400435131369957050799 e = 130055004464808383851466991915980644718382040848563991873041960765504627910537316320531719771695727709826775790697704799143461018934672453482988811575574961674813001940313918329737944758875566038617074550624823884742484696611063406222986507537981571075140436761436815079809518206635499600341038593553079293254 ''' 

$$e \equiv rh+m \equiv \frac{rg}{f}+m \ (mod \ q)$$

$$\tag{2}ef = rg+mf$$

$$(ef)f^{-1}\equiv (rg+mf)f^{-1} \equiv rgf^{-1}+mff^{-1} \equiv mff^{-1}\equiv m \ (mod\ g)$$

 1 2 3 4 5 6 7 8 9  from Crypto.Util.number import long_to_bytes,inverse f = 4685394431238242086047454699939574117865082734421802876855769683954689809016908045500281898911462887906190042764753834184270447603004244910544167081517863 g = 5326402554595682620065287001809742915798424911036766723537742672943459577709829465021452623299712724999868094408519004699993233519540500859134358256211397 q = 172620634756442326936446284386446310176482010539257694929884002472846127607264743380697653537447369089693337723649017402105400257863085638725058903969478143249108126132543502414741890867122949021941524916405444824353100158506448429871964258931750339247018885114052623963451658829116065142400435131369957050799 e = 130055004464808383851466991915980644718382040848563991873041960765504627910537316320531719771695727709826775790697704799143461018934672453482988811575574961674813001940313918329737944758875566038617074550624823884742484696611063406222986507537981571075140436761436815079809518206635499600341038593553079293254 m = (e*f % q) % g m *= inverse(f, g) print(long_to_bytes(m % g)) # y0u_ar3_s0_f@st 

从公钥得到私钥

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22  from gmpy2 import iroot, sqrt from Crypto.Util.number import * q = 126982824744410328945797087760338772632266265605499464155168564006938381164343998332297867219509875837758518332737386292044402913405044815273140449332476472286262639891581209911570020757347401235079120185293696746139599783586620242086604902725583996821566303642800016358224555557587702599076109172899781757727 h = 31497596336552470100084187834926304075869321337353584228754801815485197854209104578876574798202880445492465226847681886628987815101276129299179423009194336979092146458547058477361338454307308727787100367492619524471399054846173175096003547542362283035506046981301967777510149938655352986115892410982908002343 e = 81425203325802096867547935279460713507554656326547202848965764201702208123530941439525435560101593619326780304160780819803407105746324025686271927329740552019112604285594877520543558401049557343346169993751022158349472011774064975266164948244263318723437203684336095564838792724505516573209588002889586264735 def gaussian(v1, v2): while True: if sqrt(v2[0]**2+v2[1]**2) < sqrt(v1[0]**2+v1[1]**2): v1, v2 = v2, v1 m = int((v1[0]*v2[0]+v1[1]*v2[1])/(v1[0]**2+v1[1]**2)) if m == 0: return (v1, v2) v2 = [v2[0]-m*v1[0], v2[1]-m*v1[1]] s1, s2 = gaussian([1, h], [0, q]) f, g = s1[0], s1[1] m = (e*f % q) % g m *= inverse(f, g) print(long_to_bytes(m % g)) # l1Ii5n0tea5y