> For the complete documentation index, see [llms.txt](https://kos0ng.gitbook.io/ctfs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kos0ng.gitbook.io/ctfs/write-up/2023/ascis-quals/cryptography.md).
# Cryptography
## WELCOME RSA (100 pts)
### Description
\-
### Solution
Given source code below
```python
#!/usr/bin/python3
from Crypto.Util.number import getPrime
from Crypto.Util.number import bytes_to_long
N = 1024
p = getPrime(N)
q = getPrime(N)
m = 0
with open('flag.txt', 'rb') as f:
m = bytes_to_long(f.read())
e = 65537
phi = (p-1) * (q-1)
c_p = pow(m, e, p)
c_q = pow(m, e, q)
print(f"c_p = {c_p}")
print(f"c_q = {c_q}")
print(f"N = {p * q}")
print(f"phi = {phi}")
```
What we have:
* c\_p = m^e mod p
* c\_q = m^e mod q
* n = p \* q
* phi = (p-1)\*(q-1)
We can get p and q by utilizing phi and n
$$
(p-1)(q-1) = pq - p - q + 1\\
(p-1)(q-1) = n - (p + q) + 1\\
p + q = n - phi + 1
$$
After getting p+q we can put it on quadratic equation
$$
x^2 - bx + c = 0\\
x^2 - (p+q)x + pq = 0
$$
Finally, with asumption that m < p, we can decrypt it by only using p.
```python
from Crypto.Util.number import *
c_p = 70770563170413485640234825332830715579644049285355981293505262738914209029517352373077018947770320280278746620671203215024503799950910898732397153179084074098233352980719945417330407037538618730258842372338429001603903091610752262516741188853590089951756761811040256580538917054394236602707893767220570272331
c_q = 13851492318566804426180559171717895114036816324429566434285593612538644178623395941843619351600718862105589158342528216101368809170495598383990497387251379469346455961514711553702647806756877972791529391358173595919397389755049646932111264878041754835352170573649918876911510785389021472942167961552938040890
N = 19694268725205416932271364425385420707850329840157673295273677195054630515982058976079498206887037469237238398405928480684350200120501078231388088496277582527947938156849419785864562896382735306087325118435609429713312673380764412264707904939485238218886677027240033716280913510048689954579551621705920549746909058000987771268371934823850223213735201866888065931847369642802547725217919776237783287489769890109322726430755322073866327698639461994686267421903262258256777595366148454467865658097293146857749360141451451546041703858527691932299750797762597565953059522307802045384870886086792768277420112890024197381341
phi = 19694268725205416932271364425385420707850329840157673295273677195054630515982058976079498206887037469237238398405928480684350200120501078231388088496277582527947938156849419785864562896382735306087325118435609429713312673380764412264707904939485238218886677027240033716280913510048689954579551621705920549746628074068680399113370686212746795530576012850939713222911207509162211597032002438837189193853944160004364194868287701610512383924569996771883743351575199994707067296109349832389723176764968511964606092023026149281647383744920057620837615083525637277639792424720226658009593127619853405831534160987224728925500
e = 65537
p_plus_q = N + 1 - phi
R, x = QQ['x'].objgen()
f = x^2 - (p_plus_q*x) + N
roots = f.roots()
p, _ = roots[0]
q, _ = roots[1]
assert p*q == N
d = pow(e, -1, p-1)
print(long_to_bytes(pow(c_p, d, p)))
```
Flag: ASCIS{W3lc0me\_t0\_th3\_P4rty\_8597b0394054835f80ebd573a238ddbe1d86942657a59a7b6f84660d629472b5}
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:
```
GET https://kos0ng.gitbook.io/ctfs/write-up/2023/ascis-quals/cryptography.md?ask=&goal=
```
`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.