# RAS
## Description
[RAS](https://asisctf.com/tasks/RAS_4e2b7ccee334c091280d6bb9ff9d15b6b7f69528.txz) is an ancient RSA like challenge for Christmas Day!
`ras.py`:```python#!/usr/bin/env python3
from Crypto.Util.number import *from flag import flag
def genparam(nbit):	while True:		a, b = getRandomRange(2, nbit), getRandomRange(32, nbit)		if (a ** b).bit_length() == nbit:			return a ** b
def genkey(nbit):	p, q = [_ + (_ % 2) for _ in [genparam(nbit) for _ in '01']]	while True:		P = p + getPrime(31)		if isPrime(P):			while True:				Q = q + getPrime(37)				if isPrime(Q):					return P, Q
def encrypt(m, pubkey):	e = 0x10001	assert m < pubkey	c = pow(m, e, pubkey)	return c
nbit = 512P, Q = genkey(nbit)pubkey = P * Qflag = bytes_to_long(flag)enc = encrypt(flag, pubkey)print(f'pubkey = {pubkey}')print(f'enc = {enc}')```
`output.txt`:```pubkey = 56469405750402193641449232753975279624388972985036568323092258873756801156079913882719631252209538683205353844069168609565141017503581101845476197667784484712057287713526027533597905495298848547839093455328128973319016710733533781180094847568951833393705432945294907000234880317134952746221201465210828955449enc = 11104433528952071860984483920122173351342473018268740572598132083816861855404615534742178674185812745207876206939230069251889172817480784782618716608299615251541018034321389516732611030641383571306414414804563863131355221859432899624060128497648444189432635603082478662202695641001726208833663163000227827283```
## Writeup
In order to find `p` and `q` we test all of the possible values of `a` and `b` of `genparam` function:
```pythonfrom Crypto.Util.number import isPrime
N = 56469405750402193641449232753975279624388972985036568323092258873756801156079913882719631252209538683205353844069168609565141017503581101845476197667784484712057287713526027533597905495298848547839093455328128973319016710733533781180094847568951833393705432945294907000234880317134952746221201465210828955449
def getb(a):    lower = 500 // (a.bit_length())    for b in range(lower, 1000):        num = a ** b        if num.bit_length() == 512:            return b        if num.bit_length() > 512:            return -1
def solve():    cands = []    for a in range(2, 513):        b = getb(a)        if b not in range(32, 513):            continue        cands.append((a, b))
    print(len(cands))    ans = []    for a in cands:        le = a[0] ** a[1]        le += le % 2        for b in cands:            ri = b[0] ** b[1]            ri += ri % 2
            if le * ri < N and (N - le * ri).bit_length() < 600:                ans.append((a, b))
    print('Count:', len(ans))    print('\n'.join(map(str, ans)))
if __name__ == '__main__':    solve()```
`genb` receives a variable `a` and returns a value of `b` such that `a**b` has 512 bits.
We find all such `(a,b)` pairs. Also, we know that `N` has about 1024 bits, but `N - p * q` will have less than 600 bits. So we do this additional test and will see that only one choice for `{p,q}` will remain at last.
Then we execute the following code to find `P`.We should run this code twice(one instance for each of the obtained 512-bit numbers)in parallel in order to find the 31 bit prime sooner.
```pythonN = 56469405750402193641449232753975279624388972985036568323092258873756801156079913882719631252209538683205353844069168609565141017503581101845476197667784484712057287713526027533597905495298848547839093455328128973319016710733533781180094847568951833393705432945294907000234880317134952746221201465210828955449start = int(input())cnt = 0rem = 1 << 20
for i in range(2**30+1, 2**31, 2):    rem -= 1    if rem == 0:        rem = 1 << 20        cnt += 1        print(cnt)    if i % 6 in [1, 5] and N % (start + i) == 0:        print(i)        break```
Note that:
* The `rem` and `cnt` variables are used to monitor the progress. They don't play a role in finding proper i value* The `i % 6 in [1, 5]` is a weak test on `i` to be prime and improve the speed of the code.* For loop step length is 2 as `i` should be prime and thus not an even number.
In the case of `23**113 + 1` input to the code, it will print `1158518719` in the 40th step. So we add this value to `23**113 + 1` to obtain `P` and then divide `N` by `P` to obtain `Q`.
```pythonfrom Crypto.Util.number import long_to_bytes
N = 56469405750402193641449232753975279624388972985036568323092258873756801156079913882719631252209538683205353844069168609565141017503581101845476197667784484712057287713526027533597905495298848547839093455328128973319016710733533781180094847568951833393705432945294907000234880317134952746221201465210828955449P = 23**113 + 1 + 1158518719Q = N // Penc = 11104433528952071860984483920122173351342473018268740572598132083816861855404615534742178674185812745207876206939230069251889172817480784782618716608299615251541018034321389516732611030641383571306414414804563863131355221859432899624060128497648444189432635603082478662202695641001726208833663163000227827283
phi = (P - 1) * (Q - 1)d = pow(0x10001, -1, phi)print(long_to_bytes(pow(enc, d, N)).decode())```
It will print `ASIS{RAS_iZ_51mpl!FI3D_RSA_sY573M!}`