Tags: crypto

Rating: 2.0

Because this is just basic RSA, so I just show code and every computing I commented in this code !
py
import math
from Crypto.Util.number import *
#############
_1_50 = 1 << 50 # 2**50 == 1,125,899,906,842,624

def isqrt(x):
"""Return the integer part of the square root of x, even for very
large integer values."""
if x < 0:
raise ValueError('square root not defined for negative numbers')
if x < _1_50:
return int(math.sqrt(x)) # use math's sqrt() for small parameters
n = int(x)
if n <= 1:
return n # handle sqrt(0)==0, sqrt(1)==1
# Make a high initial estimate of the result (a little lower is slower!!!)
r = 1 << ((n.bit_length() + 1) >> 1)
while True:
newr = (r + n // r) >> 1 # next estimate by Newton-Raphson
if newr >= r:
return r
r = newr
#############
e=65537
s = 518521484172073259043145502034694599512935443283076107003494840643504150663248402410462928864122818999731280619095755616648044687630285476363367234348295346345048643618601901838740100
n = 121789376487960809489253386587170686658768726657045553214623415992384832614485249137256874454267032401365173859563210814953487893574413409932117585950570225259024509903129746392143101
a = 14910
b = 1443061772954701335732136128869248910288995712185482317126411260349775148932784597588115548780067761993841192961205698418501468762734686695975550561598140253475710348439640002745286347562
ciphertext = [95844532553991737600355244654272099305361975575150371319709729091243030203575898742071987199800250922501746626433985253038713853151746857514762678605619742310839669559545627531098676, 42098262117872607180245376226279234844537189667792611290978137770131205295202393318329675438677406769928295941768074280915365884838027414974072838410934952571392616562898636004189303, 8604504123043858588289398284978073629384165878986588408956445422750740896636700840713408309772547146776823067482307495576552057400894861616123713400577813256614795674220942022738198, 66896916235028791010554130879834163456721897024453929564151545727202320039792487273512943832159287883050106923587075192390665897004465138382234040927275478139131450371794658563343368, 88176130128782413821390318550151008388570132120182664342566671328546119423517817326934034720909238554168653863093116429325532932401977519369212892117707167802400008407395125896733332, 42250039274640778630603717605163827961176577828564055370588929192401015587247485151024369147022833032549004175634147831360114651662490704138925606397505368573040950634048151235675964, 106267843822546752528780879737401351948170741446817769684516569656816005147897267321452764634553751488085440938706773625287154372645991244141121226180609731226228509942129690482744498, 7344462713592491879813960159075800353984094813742489003735150623847056840460595091048879286634691169764793649426176975158414555454778075430233699780146900520609629142406422725693811, 68155732896092345896827379516624133280166986984023541993085330906321960888421556683672078055376548346464764100036149614632795220030187229733989823788323988946361921828069707823065198, 2456638129741631242062051214133833843357605035108383884677777076160879939756985403557604264648903511528401478876871578775440101482814072714355366084122429853207060638683606389504551, 99671982271645788903414016384550975165361965345980177928115018027271173062935625698434769263846972984813377601618481025600240081090732166957299336765744471217496851539810214590361856]
# print(len(ciphertext))
# s = (p+q)^2
# n = p*q
#=> can_s = p+q ; n=p*q
can_s = isqrt(s)
#p*(can_s-p)=n <=> p^2 - p*can_s + n = 0
_a = 1
_b = -can_s
_c = n
delta = _b*_b - 4*_a*_c
can_delta = isqrt(delta)
q = (can_s + can_delta)//2
p = n//q
# print(p)
# print(q)
##############################Done calculate p,q #############
# s^3 = a (mod r)
# b = (s-q*(2*p+q))*r => r = b // (s-q*(2*p+q))

mixed = (s-q*(2*p+q))
r = b//mixed
#############Done Calculate r #################

#(m[i]*r)^e = c[i] (mod n)
#phi = (p-1)*(q-1)
# d = e^(-1) (mod phi)
# (m[i]*r) = c[i]^(d) (mod n)
# => m[i] = r^(-1)*c[i]^(d) (mod n)
def solve():
phi = (p-1)*(q-1)
d = inverse(e,phi)
mm=[]
for _c in ciphertext:
_m = inverse(r,n)*pow(_c,d,n)
_m = _m%n
mm.append(_m)
for _m in mm:
print(long_to_bytes(_m))

solve()

##############TEST ########
# if(pow(s,3,r)==a):
# print("Y")
# if(b%mixed==0):
# print("Y")

#############Tiep tuc pha an ###################
# b"#Snab says good job! But you're not done yet\n"
# b'flag = findme\n'
# b"halfa = ''.join([flag[i] for i in range (0, len(flag), 2)])\n"
# b"halfb = ''.join([flag[i] for i in range (1, len(flag), 2)]\n"
# b"p = bytes_to_long(bytes(halfa, encoding = 'utf-8'))\n"
# b"q = bytes_to_long(bytes(halfb, encoding = 'utf-8'))\n"
# b'r = 0\n'
# b'while (not(isPrime(p) and isPrime(q))):\n'
# b' p += 1\n'
# b' q += 1\n'
# b' r += 1\n'

#p_goc = p-1
#q_goc = q-1
p_goc = p-r
q_goc = q-r
# while(isPrime(p) and isPrime(q)):
# p-=1
# q-=1

# print(long_to_bytes(p_goc))
# print(long_to_bytes(q_goc))
half_a = long_to_bytes(p_goc)
half_b = long_to_bytes(q_goc)
# print(len(half_a))
# print(len(half_b))
# print(chr(half_a[0]))

# res=res + chr(half_a[0])
# for i in half_b:
# print(chr(i))
def solve1():
res=""
i=0
dem1=0
dem2=0
while(1):
if(dem1==len(half_a) and dem2==len(half_b)):
break
if(i%2==0):
res=res+ chr(half_a[dem1])
dem1+=1
else:
res=res+ chr(half_b[dem2])
dem2+=1
i+=1
print(res)
solve1()
# print(res)