Tags: cryptography-rsa crypto rsa
Rating:
# Sausage Links - 468pt
----------------------------------------
## Topic summary
This problem gives us two files, one is `output.txt` and the other is `sausage_links.py`. As follows:
### sausage_links.py
```py
#!/usr/bin/env python3
from gmpy import *
from Crypto.Util.number import *
import gensafeprime
flag = open("flag.txt", "rb").read().strip()
bits = 512
p = getPrime(bits)
q = getPrime(bits)
r = getPrime(bits)
n = p * q * r
phi = (p - 1) * (q - 1) * (r - 1)
l = min([p, q, r])
d = getPrime(1 << 8)
e = inverse(d, phi)
a = gensafeprime.generate(2 * bits)
while True:
g = getRandomRange(2, a)
if pow(g, 2, a) != 1 and pow(g, a // 2, a) != 1:
break
pubkey = (n, e, a, g)
m = bytes_to_long(flag)
k = getRandomRange(2, a)
K = pow(g, k, a)
c1, c2 = pow(k, e, n), (m * K) % a
print("c =", (c1, c2))
print("pubkey =", pubkey)
```
----------------------------------------------------------------------------------------------------------
### output.txt
```txt
c = (75393472403093883980765814047645327405215775478712827591109646890837780762923959326166827649826238535312344488349557712816610930220370001305827412505043127914547998320440240250325118053813714466854788644697706490515892504619105361332594358021214992759872975638137819189634434255388142452402903984216170592454070190763219802978580474823882279160692450914521162374808790341598702288608920814072249086450656427949215063564752988546802554974565217418056403485189158, 21743667484649294456505545386313391146296096106309721435244191430622536536241638911796782012089471615188229556482084132221324157541121095745921331613424302593658426094356838716843005440373679746518683613229280959080885966038959064524609397524131981550731325678855657987757274636339648236504515056989339931829)
pubkey = (549935778300831378406948873536278349781214706503360745280597408861216877781142622004454148443526758471040653633080987617044763942008023466559253761306561736450658314626615456982873023501736081710037081947666247132668118860186965548713647775109193997705890766881191577188287773692953347103686449329398217311195051172403636510262250822460785125486925931569891688688353900466632582649417645956790937903144901696446727579207702041958066277574559994377445136251040659, 32204951698260962458157592984992469529416584332675382497988021285424821386904232277036373403101864193040613563796784569698857185940927175841205145358641690922026788366581684507467056308764343250379771013177468030580725648480591696059317745554974780583562695962973324819593002957827750301174079447431501960032717699255546396631743680242345092881301693065171460311485778344053788138555054294470951574964376432654831106364396876336137419860163278539415409181597819, 138573907982913094895957560613895338045899660024192238553307135243826517727787057358804422211354202143617168828075979083404334708411832425604299257351876162289412352723963051979157876631398717413563591084855571688469543441655488090919934371369975426760135367341463974144518915155974937301498827086824773106003, 68759670662427533761108453255036749386266492702870615501799248175187816213782210092795089989860635666887242761904219513870052421033161791299816761321508643099537034976789844586576430337882832633194279669183386905734135409454252901918801636934986951843672112043695989089719222626801371853255674748960081747148)
```
----------------------------------------------------------------------------------------------
### List the facts of the problem
+
+
+
+ is a prime number
bits
+
+ is a prime number (
bit)
+ is random satisfied:
and
+ is random in range
+
+
+
### The problem is for the parameters . Our task is to find
so that we can deduce the flag we want to find
-----------------------------------------------------------------------------
Here is our team's solution, we notice that, here is quite large and
is a relatively small number, so our team approached the problem by using weiner method to find
. Fortunately, we managed to find two values of
, and from there using trial and error we found the flag.
#### Attack's weiner
```py
from sage.all import Integer
from sage.all import continued_fraction
#from factorization import known_phi
e = 32204951698260962458157592984992469529416584332675382497988021285424821386904232277036373403101864193040613563796784569698857185940927175841205145358641690922026788366581684507467056308764343250379771013177468030580725648480591696059317745554974780583562695962973324819593002957827750301174079447431501960032717699255546396631743680242345092881301693065171460311485778344053788138555054294470951574964376432654831106364396876336137419860163278539415409181597819
n = 549935778300831378406948873536278349781214706503360745280597408861216877781142622004454148443526758471040653633080987617044763942008023466559253761306561736450658314626615456982873023501736081710037081947666247132668118860186965548713647775109193997705890766881191577188287773692953347103686449329398217311195051172403636510262250822460785125486925931569891688688353900466632582649417645956790937903144901696446727579207702041958066277574559994377445136251040659
c1 = 75393472403093883980765814047645327405215775478712827591109646890837780762923959326166827649826238535312344488349557712816610930220370001305827412505043127914547998320440240250325118053813714466854788644697706490515892504619105361332594358021214992759872975638137819189634434255388142452402903984216170592454070190763219802978580474823882279160692450914521162374808790341598702288608920814072249086450656427949215063564752988546802554974565217418056403485189158
c2 = 21743667484649294456505545386313391146296096106309721435244191430622536536241638911796782012089471615188229556482084132221324157541121095745921331613424302593658426094356838716843005440373679746518683613229280959080885966038959064524609397524131981550731325678855657987757274636339648236504515056989339931829
a = 138573907982913094895957560613895338045899660024192238553307135243826517727787057358804422211354202143617168828075979083404334708411832425604299257351876162289412352723963051979157876631398717413563591084855571688469543441655488090919934371369975426760135367341463974144518915155974937301498827086824773106003
g = 68759670662427533761108453255036749386266492702870615501799248175187816213782210092795089989860635666887242761904219513870052421033161791299816761321508643099537034976789844586576430337882832633194279669183386905734135409454252901918801636934986951843672112043695989089719222626801371853255674748960081747148
def attack(n, e):
"""
Recovers the prime factors of a modulus and the private exponent if the private exponent is too small.
:param n: the modulus
:param e: the public exponent
:return: a tuple containing the prime factors of the modulus and the private exponent, or None if the private exponent was not found
"""
convergents = continued_fraction(Integer(e) / Integer(n)).convergents()
for c in convergents:
k = c.numerator()
d = c.denominator()
if k == 0 or (e * d - 1) % k != 0:
continue
print("d",d)
attack(n,e)
```
And this is values of
we found
~~~
d=17
d=105139577487193794924679137792353224445415748360286951415614751393941533449299
~~~
Once was found, everything became a basic RSA problem, and the specific computation was as follows:
+
+
+
#### This is code to find m
```py
from Crypto.Util.number import *
from math import sqrt
c = [75393472403093883980765814047645327405215775478712827591109646890837780762923959326166827649826238535312344488349557712816610930220370001305827412505043127914547998320440240250325118053813714466854788644697706490515892504619105361332594358021214992759872975638137819189634434255388142452402903984216170592454070190763219802978580474823882279160692450914521162374808790341598702288608920814072249086450656427949215063564752988546802554974565217418056403485189158, 21743667484649294456505545386313391146296096106309721435244191430622536536241638911796782012089471615188229556482084132221324157541121095745921331613424302593658426094356838716843005440373679746518683613229280959080885966038959064524609397524131981550731325678855657987757274636339648236504515056989339931829]
pubkey = [549935778300831378406948873536278349781214706503360745280597408861216877781142622004454148443526758471040653633080987617044763942008023466559253761306561736450658314626615456982873023501736081710037081947666247132668118860186965548713647775109193997705890766881191577188287773692953347103686449329398217311195051172403636510262250822460785125486925931569891688688353900466632582649417645956790937903144901696446727579207702041958066277574559994377445136251040659, 32204951698260962458157592984992469529416584332675382497988021285424821386904232277036373403101864193040613563796784569698857185940927175841205145358641690922026788366581684507467056308764343250379771013177468030580725648480591696059317745554974780583562695962973324819593002957827750301174079447431501960032717699255546396631743680242345092881301693065171460311485778344053788138555054294470951574964376432654831106364396876336137419860163278539415409181597819, 138573907982913094895957560613895338045899660024192238553307135243826517727787057358804422211354202143617168828075979083404334708411832425604299257351876162289412352723963051979157876631398717413563591084855571688469543441655488090919934371369975426760135367341463974144518915155974937301498827086824773106003, 68759670662427533761108453255036749386266492702870615501799248175187816213782210092795089989860635666887242761904219513870052421033161791299816761321508643099537034976789844586576430337882832633194279669183386905734135409454252901918801636934986951843672112043695989089719222626801371853255674748960081747148]
c1 = c[0]
c2 = c[1]
n = pubkey[0]
e = pubkey[1]
a = pubkey[2]
g = pubkey[3]
# print(e)
e = 32204951698260962458157592984992469529416584332675382497988021285424821386904232277036373403101864193040613563796784569698857185940927175841205145358641690922026788366581684507467056308764343250379771013177468030580725648480591696059317745554974780583562695962973324819593002957827750301174079447431501960032717699255546396631743680242345092881301693065171460311485778344053788138555054294470951574964376432654831106364396876336137419860163278539415409181597819
n = 549935778300831378406948873536278349781214706503360745280597408861216877781142622004454148443526758471040653633080987617044763942008023466559253761306561736450658314626615456982873023501736081710037081947666247132668118860186965548713647775109193997705890766881191577188287773692953347103686449329398217311195051172403636510262250822460785125486925931569891688688353900466632582649417645956790937903144901696446727579207702041958066277574559994377445136251040659
c1 = 75393472403093883980765814047645327405215775478712827591109646890837780762923959326166827649826238535312344488349557712816610930220370001305827412505043127914547998320440240250325118053813714466854788644697706490515892504619105361332594358021214992759872975638137819189634434255388142452402903984216170592454070190763219802978580474823882279160692450914521162374808790341598702288608920814072249086450656427949215063564752988546802554974565217418056403485189158
c2 = 21743667484649294456505545386313391146296096106309721435244191430622536536241638911796782012089471615188229556482084132221324157541121095745921331613424302593658426094356838716843005440373679746518683613229280959080885966038959064524609397524131981550731325678855657987757274636339648236504515056989339931829
a = 138573907982913094895957560613895338045899660024192238553307135243826517727787057358804422211354202143617168828075979083404334708411832425604299257351876162289412352723963051979157876631398717413563591084855571688469543441655488090919934371369975426760135367341463974144518915155974937301498827086824773106003
g = 68759670662427533761108453255036749386266492702870615501799248175187816213782210092795089989860635666887242761904219513870052421033161791299816761321508643099537034976789844586576430337882832633194279669183386905734135409454252901918801636934986951843672112043695989089719222626801371853255674748960081747148
d = 105139577487193794924679137792353224445415748360286951415614751393941533449299
print("len a",len(str(a)))
print(len(str(d)))
k = pow(c1,d,n)
print("len k",len(str(k)))
if(k
