vindica.sageVindicaSimple multiplications with almost small matrices is still fun! Help Vindica to do precise operation.
#!/usr/bin/env sage
from Crypto.Util.number import *
from flag import flag
def genkey(nbit, k):
p = getPrime(nbit)
q = getPrime(nbit >> 2)
n = p * q
N = (p**k - 1) * (q**k - 1)
while True:
e = getRandomRange(1, n)
if gcd(e, n * N) == 1:
pkey = e, n, N
skey = p, q
return (pkey, skey)
def two_layencrypt(msg, pkey):
e, n, _ = pkey
Zn = Zmod(n)
m = bytes_to_long(msg)
c = pow(m, e, n)
_c = str(c)
l = len(_c)
_C = matrix(Zn, [[_c[:l//4], _c[l//4:l//2]], [_c[l//2:3*l//4], _c[3*l//4:l]]])
assert gcd(det(_C), n) == 1
C = _C ** e
return C
k, nbit = 2, 1024
pkey, skey = genkey(nbit, k)
e, n, N = pkey
C = two_layencrypt(flag, pkey)
print(f'e = {e}')
print(f'n = {n}')
print(f'N = {N}')
print(f'C = {C}')
solve.sage
from Crypto.Util.number import *
e = 5078482198772022486668806580385994617046152136879757946447753006497559096311363698189927671279662282460215881884971383977603769421560651587643105884432120505614024093712045492181196774755153389551488415626903341200511584895756666520506685233571091301553677432797291383522948247421577307790421871576621793242903515091500045988509062949276333178982069574732477506029694357450058826765713
n = 10363021449027481978397698136523040156224840526536988813980447772289732568252796583569029480400841885971918279457292628777077494964266272306073795156837303451597151870070735534829041207628743246817464229192036030566123925737361164838906363407544870946204200850305741513829976332440459648804252085931138269521493971098766209511334573046832632919268929658929293913408444131177270388104753
N = 107392213553003652264193356141167842390327964666141411489753605300895389967717966219065325990583863026846677998499640622335255057106717292127317146400275358099599424428452765008928717339373244201449378568575832746100164090683550257574318731278439068909731202915200677410600049491303490567787820558996671108309423176089895240263790586705493906801778186252566858325220004019042683750828880339778401860112372011304892642369252185945127428055544519414082092350188418631467500702136331749454574303277689214044524567187394949387563389853123501460406372967215083941957639592408343405520031691298337072435702126794068748777393361487701429744483153095410562309113676977172598678391507488125481975026270733267725691293233008326251906894300961329722446578580183117531847748965008640
C = [[1946208174139816651741710263419547576592153126350801855142762133627913647508863455823382709899043259671094044028462261991810476672592342389139600583419037130249400429216051912147809156497388747490389535839278095179701275637029504452920313532785460709421810335322833683324583540542971635153116319417565879782567743525221686507906726087786621105169291168378964690052819764946613598283697,
1132182340479698114482383874952797406851835394503617195832358500522890480350948370033970794090094723318039532275191223723742462388681999900392328756181997298887891875712789491584405574822571967927609744519369790826014436738457000983543164898860473898076283762333186668689272789942682725689777116575064398495040777661209346469818796761610299917869552187462992078953932871607107940428566],
[7700452780560041441552917813890524163110993823471424265020074756508053970669942522256608739094119235303843336659577921739326977145056801702083374978356129281255531665001370179699899093743464696424465158478872708449905227751200590864428048833098665065609353140089197777268079240074549285218684722855590774839476140179718516214563523243006229792289296462740200370706099145614178211440202,
7782708893953874570747318809245408011800629307006741721998241910864916749737624604100584864398704986546325867550058017705502633594608936861884411666933396887981901979859722266987588797058800525120021500545010297268991183937262790320218011315696953115130360268521260963297555084965631546139006069842106143556094168429235033227360856462499208085105421810405108260458185350930612978313221]]
Zn = Zmod(n)
C = matrix(Zn, 2, 2, C)
_C = C ** inverse_mod(e, N)
l00 = len(str(_C[0][0]))
l01 = len(str(_C[0][1]))
l10 = len(str(_C[1][0]))
l11 = len(str(_C[1][1]))
print(l00, l01, l10, l11)
_l = l00 + l01 + l10 + l11
for _ in range(10):
_l00 = _l//4
_l01 = _l//2 - _l//4
_l10 = _l*3//4 - _l//2
_l11 = _l - _l*3//4
print(_l00, _l01, _l10, _l11)
_c = "0"*(_l00-l00)+str(_C[0][0]) + "0"*(_l01-l01)+str(_C[0][1]) + "0"*(_l10-l10)+str(_C[1][0]) + "0"*(_l11-l11)+str(_C[1][1])
l = len(_c)
c = int(_c)
m = power_mod(c, inverse_mod(e, N), n)
msg = long_to_bytes(m)
print(msg)
if b"ASIS" in msg:
break
_l+=1
96 95 95 9795 96 96 96b'\r\xe9\xd1\x86=\xe5\x9d\x93\xa8\x90\x92\xfd \x0e\xfa\xb2\xdb\xa4q.(\xc8)~^Oz\x0f\xde\xac\x0f"\xeb\x1a{\x82(\x7f\x94\xc5\xc7\r\x9e\xc7\xb3U\x8b\xc9\xdaOS4\\\x19\xbcA\x8fD\x93\xa3\xfe\xcb\x90\n_6c\x11\xcb|S\x86G\xdbr\xac\xfe%aK\x14\xf6\x08\t\xfb\xf1\x10\xae\x88\xb5^\xd3\xaf\xa0\xd7\x8e\x01U`\x97N?\xadl\xdf\x88w\xf1\x87%\xd0\xd6\x94\x0e\x1d \xb9}0\xba\xa6\xc36\xda7\xc5\x80\x8b\x99o\x06\xc5\x91\xd0\xfa\xb3\x08c\xd1\xcb\xe5Y\xfd\xe4s\x05\xa68z3\x10Px\x84(\n\xf2K\xe2\x8a'96 96 96 96b'\r\xe9\xd1\x86=\xe5\x9d\x93\xa8\x90\x92\xfd \x0e\xfa\xb2\xdb\xa4q.(\xc8)~^Oz\x0f\xde\xac\x0f"\xeb\x1a{\x82(\x7f\x94\xc5\xc7\r\x9e\xc7\xb3U\x8b\xc9\xdaOS4\\\x19\xbcA\x8fD\x93\xa3\xfe\xcb\x90\n_6c\x11\xcb|S\x86G\xdbr\xac\xfe%aK\x14\xf6\x08\t\xfb\xf1\x10\xae\x88\xb5^\xd3\xaf\xa0\xd7\x8e\x01U`\x97N?\xadl\xdf\x88w\xf1\x87%\xd0\xd6\x94\x0e\x1d \xb9}0\xba\xa6\xc36\xda7\xc5\x80\x8b\x99o\x06\xc5\x91\xd0\xfa\xb3\x08c\xd1\xcb\xe5Y\xfd\xe4s\x05\xa68z3\x10Px\x84(\n\xf2K\xe2\x8a'96 96 96 97b'\r\xe9\xd1\x86=\xe5\x9d\x93\xa8\x90\x92\xfd \x0e\xfa\xb2\xdb\xa4q.(\xc8)~^Oz\x0f\xde\xac\x0f"\xeb\x1a{\x82(\x7f\x94\xc5\xc7\r\x9e\xc7\xb3U\x8b\xc9\xdaOS4\\\x19\xbcA\x8fD\x93\xa3\xfe\xcb\x90\n_6c\x11\xcb|S\x86G\xdbr\xac\xfe%aK\x14\xf6\x08\t\xfb\xf1\x10\xae\x88\xb5^\xd3\xaf\xa0\xd7\x8e\x01U`\x97N?\xadl\xdf\x88w\xf1\x87%\xd0\xd6\x94\x0e\x1d \xb9}0\xba\xa6\xc36\xda7\xc5\x80\x8b\x99o\x06\xc5\x91\xd0\xfa\xb3\x08c\xd1\xcb\xe5Y\xfd\xe4s\x05\xa68z3\x10Px\x84(\n\xf2K\xe2\x8a'96 97 96 97b'ASIS{m4Tr!X_M0D1fIcA7iOn_0F_RSA_12431!}'
