TSGCTF 2021

Note : A JOURNEY TO GAIN KNOWLEDGE

#Beginner's Crypto 2021

from secret import e
from Crypto.Util.number import getStrongPrime, isPrime

p = getStrongPrime(1024)
q = getStrongPrime(1024)
N = p * q
phi = (p - 1) * (q - 1)

with open('flag.txt', 'rb') as f:
    flag = int.from_bytes(f.read(), 'big')

assert(isPrime(e))
assert(isPrime(e + 2))
assert(isPrime(e + 4))

e1 = pow(e, 0x10001, phi)
e2 = pow(e + 2, 0x10001, phi)
e3 = pow(e + 4, 0x10001, phi)

c1 = pow(flag, e1, N)
c2 = pow(flag, e2, N)
c3 = pow(flag, e3, N)

print(f'p = {p}')
print(f'q = {q}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')

# p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
# q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
# c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
# c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
# c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837

Đề cho e, e+2,e+4 là số nguyên tố nên e chỉ có thể là 3, vì những số lớn hơn khoảng cách giữa các số nguyên tố là rất lớn. Từ đó giải theo hướng Common modulus (same n) - External Attack .

from Crypto.Util.number import *
from gmpy2 import *

n = 21861849068488503326777564160482917768295313612622098844005843941150416001449415831637974753612296634178937206635448545759776608072919261837704109903460487852321593647461325194355863907156869648747188133965073402040821653255878590888415203522221544646026084652799982648089185458004128592803363049028863875147302298032914963095395238481777617108444373792690712586751618914946813447656100899378283397273293143842550921101844777123910587444282360703980995288785551256271451760332791447461673193550567714926450717517656392539447836755985235708569019532947491148812339977048504141761177263545250566883133462383528417086483
e1 = 17603549263186425341767929511665789959105944330977732610916014873119252282802636800619943218173617441888097241786330044467390706899621342311537780960325827434196373002926945337049116646768167280435578161313136166984912128140809491969353494782750474301810262688555936515237213157072589888855009082917459841124317212785314003914313234917639294833196462895550624990993855672424098551845194332818039618333455201098641549770441114401683833649029496333471721218422923953911572405255917219368996940141028493863221349007615701640977231767979869511746450459020309485973427107977390630775364092661966159756765434661573566462163
e2 = 15344508209087520408904622039612403292778077018374460918944647544769165640337137582186403919710159968904923421386737007919512784139878000070417785469235072760767520470631932153936681007172335035560603688152851363757551810390163356371161738851859293395985292893266642634947470905628261585873301406883399307465584080339646976686630070325570603080476048485894627862169328144852580941394727582550746753409269261023938462291893093488806622999431476759128322955553737212823603838438441286632412590780859732560765318694595239577819399088507513384628815021733400052028849608900698718593489414974683054465037065557915104359925
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743

_, u, v = gcdext(e1, e2)

if u < 0: # if u < 0, compute c1_inv
	c1_inv = invert(c1, n)
	M = (c1_inv**(-u) * c2**v) % n
else:
	c2_inv = invert(c2, n)
	M = (pow(c2_inv,(-v),n) * pow(c1,u,n)) % n

print (long_to_bytes(M))

# b'TSGCTF{You are intuitively understanding the distribution of prime numbers! Bonus: You can solve this challenge w/ N instead of p and q!}'

#Minimalist's Private

from Crypto.Util.number import isPrime
from random import randrange
from secret import p, q, L, e, d

class RSA:
    def __init__(self, p, q, L, e, d):
        assert(isPrime(p) and isPrime(q))
        self.N = p * q
        self.L = L
        self.e = e
        self.d = d

        # these are the normal RSA conditions
        for _ in range(100):
            assert(pow(randrange(1, self.N), self.L, self.N) == 1)
        assert(self.e * self.d % self.L == 1)

        # minimal is the best
        assert(self.L * self.L <= 10000 * self.N)

    def gen_private_key(self):
        return (self.N, self.d)

    def gen_public_key(self):
        return (self.N, self.e)

    def encrypt(self, msg):
        return pow(msg, self.e, self.N)

    def decrypt(self, c):
        return pow(c, self.d, self.N)

flag = open('flag.txt', 'rb').read()
msg = int.from_bytes(flag, byteorder='big')
assert(msg < p * q)

rsa = RSA(p, q, L, e, d)
encrypted = rsa.encrypt(msg)
assert(rsa.decrypt(encrypted) == msg)

print(f'N, e = {rsa.gen_public_key()}')
print(f'c = {encrypted}')
#N= 1108103848370322618250236235096737547381026108763302516499816051432801216813681568375319595638932562835292256776016949573972732881586209527824393027428125964599378845347154409633878436868422905300799413838645686430352484534761305185938956589612889463246508935994301443576781452904666072122465831585156151
#e = 65537
#c = 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426

ta thấy: lcm(p−1,q−1) = (p−1)(q−1) / gcd((p−1),(q−1))

N có 304 digits = > p,q ~ 151,153 digits nên UCLN sẽ rất lớn:

gọi: p=s*a+1 và q=s*b+1

N = p*q
  = (s*a + 1) * (s*b +1 )
  = a*b*s^2 +(a+b)*s +1
<=> a*b*s^2 +(a+b)*s +1-N == 0
# Giải pt bậc 2 tình s rồi từ đó có a,b

bruteforce a,b để tìm p,q.

Đây là code mình dùng để solve:

from Crypto.Util.number import *
from sympy import *


N= 1108103848370322618250236235096737547381026108763302516499816051432801216813681568375319595638932562835292256776016949573972732881586209527824393027428125964599378845347154409633878436868422905300799413838645686430352484534761305185938956589612889463246508935994301443576781452904666072122465831585156151
e = 65537
c = 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426

count = 0
def find_invpow(x,n):
    """Finds the integer component of the n'th root of x,
    an integer such that y ** n <= x < (y + 1) ** n.
    """
    high = 1
    while high ** n < x:
        high *= 2
    low = high//2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1

def quadratic_solve(a,b,c):
	return (-b + find_invpow(b*b - 4*a*c, 2))//(2*a)

for a in range(1, 5000):
		for b in range(1, 5000):
			G = quadratic_solve(a*b, a+b, 1 - N)
			# a*b*G^2 + (a+b)*G +1-N == 0
			p = G*a + 1
			q = G*b + 1
			if p*q == N and isprime(p) and isprime(q):
				print(p)
				print(q)
				phi = (p-1)*(q-1)
				d = pow(e, -1, phi)
				flag = long_to_bytes(pow(c, d, N))
				if b'TSGCTF' in flag:
					print(flag, a, b)
					count +=1
					break
		if count != 0:
			break
			
		print(a)

Code tối ưu hơn, mình tham khảo từ joseph:

from Crypto.Util.number import isPrime, long_to_bytes
from gmpy2 import iroot

N, e = (1108103848370322618250236235096737547381026108763302516499816051432801216813681568375319595638932562835292256776016949573972732881586209527824393027428125964599378845347154409633878436868422905300799413838645686430352484534761305185938956589612889463246508935994301443576781452904666072122465831585156151, 65537)
c = 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426

def quadratic_solve(a,b,c):
    return (-b + iroot(b*b - 4*a*c, 2)[0])//(2*a)

for a in range(1, 2**15):
    for b in range(1, 2**15):
        s = quadratic_solve(a*b, a+b, 1 - N)
        p = s*a + 1
        q = s*b + 1
        if p*q == N and isPrime(p) and isPrime(q):
            print('p:', p)
            print('q:', q)
            phi = (p-1)*(q-1)
            d = pow(e, -1, phi)
            m = pow(c, d, N)
            print(long_to_bytes(m).decode())
            exit()
# code by joseph

Thanks for reading. Have a nice day <3 .