# 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 * rphi = (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```txtc = (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 
```pyfrom sage.all import Integerfrom sage.all import continued_fraction
#from factorization import known_phie = 32204951698260962458157592984992469529416584332675382497988021285424821386904232277036373403101864193040613563796784569698857185940927175841205145358641690922026788366581684507467056308764343250379771013177468030580725648480591696059317745554974780583562695962973324819593002957827750301174079447431501960032717699255546396631743680242345092881301693065171460311485778344053788138555054294470951574964376432654831106364396876336137419860163278539415409181597819n = 549935778300831378406948873536278349781214706503360745280597408861216877781142622004454148443526758471040653633080987617044763942008023466559253761306561736450658314626615456982873023501736081710037081947666247132668118860186965548713647775109193997705890766881191577188287773692953347103686449329398217311195051172403636510262250822460785125486925931569891688688353900466632582649417645956790937903144901696446727579207702041958066277574559994377445136251040659c1 = 75393472403093883980765814047645327405215775478712827591109646890837780762923959326166827649826238535312344488349557712816610930220370001305827412505043127914547998320440240250325118053813714466854788644697706490515892504619105361332594358021214992759872975638137819189634434255388142452402903984216170592454070190763219802978580474823882279160692450914521162374808790341598702288608920814072249086450656427949215063564752988546802554974565217418056403485189158c2 = 21743667484649294456505545386313391146296096106309721435244191430622536536241638911796782012089471615188229556482084132221324157541121095745921331613424302593658426094356838716843005440373679746518683613229280959080885966038959064524609397524131981550731325678855657987757274636339648236504515056989339931829a = 138573907982913094895957560613895338045899660024192238553307135243826517727787057358804422211354202143617168828075979083404334708411832425604299257351876162289412352723963051979157876631398717413563591084855571688469543441655488090919934371369975426760135367341463974144518915155974937301498827086824773106003g = 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=17d=105139577487193794924679137792353224445415748360286951415614751393941533449299~~~
Once  was found, everything became a basic RSA problem, and the specific computation was as follows:
+ 
+ 
+ 
#### This is code to find m
```pyfrom 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 = 32204951698260962458157592984992469529416584332675382497988021285424821386904232277036373403101864193040613563796784569698857185940927175841205145358641690922026788366581684507467056308764343250379771013177468030580725648480591696059317745554974780583562695962973324819593002957827750301174079447431501960032717699255546396631743680242345092881301693065171460311485778344053788138555054294470951574964376432654831106364396876336137419860163278539415409181597819n = 549935778300831378406948873536278349781214706503360745280597408861216877781142622004454148443526758471040653633080987617044763942008023466559253761306561736450658314626615456982873023501736081710037081947666247132668118860186965548713647775109193997705890766881191577188287773692953347103686449329398217311195051172403636510262250822460785125486925931569891688688353900466632582649417645956790937903144901696446727579207702041958066277574559994377445136251040659c1 = 75393472403093883980765814047645327405215775478712827591109646890837780762923959326166827649826238535312344488349557712816610930220370001305827412505043127914547998320440240250325118053813714466854788644697706490515892504619105361332594358021214992759872975638137819189634434255388142452402903984216170592454070190763219802978580474823882279160692450914521162374808790341598702288608920814072249086450656427949215063564752988546802554974565217418056403485189158c2 = 21743667484649294456505545386313391146296096106309721435244191430622536536241638911796782012089471615188229556482084132221324157541121095745921331613424302593658426094356838716843005440373679746518683613229280959080885966038959064524609397524131981550731325678855657987757274636339648236504515056989339931829a = 138573907982913094895957560613895338045899660024192238553307135243826517727787057358804422211354202143617168828075979083404334708411832425604299257351876162289412352723963051979157876631398717413563591084855571688469543441655488090919934371369975426760135367341463974144518915155974937301498827086824773106003g = 68759670662427533761108453255036749386266492702870615501799248175187816213782210092795089989860635666887242761904219513870052421033161791299816761321508643099537034976789844586576430337882832633194279669183386905734135409454252901918801636934986951843672112043695989089719222626801371853255674748960081747148d = 105139577487193794924679137792353224445415748360286951415614751393941533449299print("len a",len(str(a)))print(len(str(d)))k = pow(c1,d,n)print("len k",len(str(k)))if(k