RSA and DLP [CRYPTO]

2 crypto challenges: RSA and Discrete Logarithm.

Challenge 1: Baby-RSA [EASY]

6 points, 576 solves

📁 Challenge Description

small numbers for small messages

output.txt

n = 10888751337932558679268839254528888070769213269691871364279830513893837690735136476085167796992556016532860022833558342573454036339582519895539110327482234861870963870144864609120375793020750736090740376786289878349313047032806974605398302398698622431086259032473375162446051603492310000290666366063094482985737032132318650015539702912720882013509099961316767073167848437729826084449943115059234376990825162006299979071912964494228966947974497569783878833130690399504361180345909411669130822346252539746722020515514544334793717997364522192699435604525968953070151642912274210943050922313389271251805397541777241902027
e = 3
c = 2449457955338174702664398437699732241330055959255401949300755756893329242892325068765174475595370736008843435168081093064803408113260941928784442707977000585466461075146434876354981528996602615111767938231799146073229307631775810351487333

🚩 Solution

This RSA challenge can be cracked using Cube Root Attack where e = 3 is too small where results in m^3 = c without undergoing modulus n.

By writing a simple script, we can get the flag easily.

#!/usr/bin/env python3
from Crypto.Util.number import long_to_bytes
from decimal import *

# n = 10888751337932558679268839254528888070769213269691871364279830513893837690735136476085167796992556016532860022833558342573454036339582519895539110327482234861870963870144864609120375793020750736090740376786289878349313047032806974605398302398698622431086259032473375162446051603492310000290666366063094482985737032132318650015539702912720882013509099961316767073167848437729826084449943115059234376990825162006299979071912964494228966947974497569783878833130690399504361180345909411669130822346252539746722020515514544334793717997364522192699435604525968953070151642912274210943050922313389271251805397541777241902027
e = 3
c = 2449457955338174702664398437699732241330055959255401949300755756893329242892325068765174475595370736008843435168081093064803408113260941928784442707977000585466461075146434876354981528996602615111767938231799146073229307631775810351487333

getcontext().prec = 100
flag = Decimal(c)**(Decimal(1)/Decimal(e))
print(long_to_bytes(int(round(flag))))
# tjctf{thr33s_4r3_s0_fun_fb23d5ed}

FLAG: tjctf{thr33s_4r3_s0_fun_fb23d5ed}

Challenge 2: EZDLP [EASY]

18 points, 188 solves

📁 Challenge Description

one easy dlp

numbers.txt

g = 8999 
s = 11721478752747238947534577901795278971298347908127389421908790123 
p = 12297383901740584470151577318651150337988716807049317851420298478128932232846789427512414204247770572072680737351875225891650166807323215624748551744377958007176198392481481171792078565005580006750936049744616851983231170824931892761202881982041842121034608612146861881334101500003915726821683000760611763097

g^x = s mod p
flag = tjctf{x}

🚩 Solution

This is my first time solving discrete logarithm problem (DLP).

The challenge gives that \(g^x \equiv s \bmod p\) and flag is tjctf{x}.

This is a DLP problem where the modulo p is not a prime and it is fully factorizable. After tons of researching in sage, we can utilize IntegerModRing() to calculate each modulus under p and discrete_log() to automate the calculation process.

#!/usr/bin/env python3
from sage.all import *

p = 12297383901740584470151577318651150337988716807049317851420298478128932232846789427512414204247770572072680737351875225891650166807323215624748551744377958007176198392481481171792078565005580006750936049744616851983231170824931892761202881982041842121034608612146861881334101500003915726821683000760611763097
g = 8999
s = 11721478752747238947534577901795278971298347908127389421908790123

R = IntegerModRing(p)
x = discrete_log(R(s), R(g))

print("tjctf{" + str(x) + "}")
# tjctf{26104478854569770948763268629079094351020764258425704346666185171631094713742516526074910325202612575130356252792856014835908436517926646322189289728462011794148513926930343382081388714077889318297349665740061482743137948635476088264751212120906948450722431680198753238856720828205708702161666784517}

FLAG: tjctf{26104478854569770948763268629079094351020764258425704346666185171631094713742516526074910325202612575130356252792856014835908436517926646322189289728462011794148513926930343382081388714077889318297349665740061482743137948635476088264751212120906948450722431680198753238856720828205708702161666784517}