# **ASIS 2022**

## Binned - Cryptography - 126 solves

### Description
> People binned to the same public ID have no real-world connection to one another.
### Attachments
- binned.py

#!/usr/bin/env python3

from Crypto.Util.number import *
from gensafeprime import *
from flag import flag

def keygen(nbit):
	p, q = [generate(nbit) for _ in range(2)]
	return (p, q)

def encrypt(m, pubkey):
	return pow(pubkey + 1, m, pubkey ** 3)

p, q = keygen(512)
n = p * q

flag = bytes_to_long(flag)
enc = encrypt(flag, n)

print(f'pubkey = {n}')
print(f'enc = {enc}')

- output.txt

pubkey = 125004899806380680278294077957993138206121343727674199724251084023100054797391533591150992663742497532376954423241741439218367086541339504325939051995057848301514908377941815605487168789148131591458301036686411659334843972203243490288676763861925647147178902977362125434420265824374952540259396010995154324589
enc = 789849126571263315208956108629196540107771075292285804732934458641661099043398300667318883764744131397353851782194467024270666326116745519739176492710750437625345677766980300328542459318943175684941281413218985938348407537978884988013947538034827562329111515306723274989323212194585378159386585826998838542734955059450048745917640814983343040930383529332576453845724747105810109832978045135562492851617884175410194781236450629682032219153517122695586503298477875749138129517477339813480115293124316913331705913455692462482942654717828006590051944205639923326375814299624264826939725890226430388059890231323791398412019416647826367964048142887158552454494856771139750458462334678907791079639005383932256589768726730285409763583606927779418528562990619985840033479201147509241313757191997545174262930707521451438204766627975109619779824255444258160

Bài này là 1 câu warm up về Toán, cụ thể như sau:

\begin{align}
(n+1)^{flag} \equiv enc \pmod{n^3}
\end{align}

Nhìn thì có vẻ giống discrete log của base $n + 1$ nhưng các bạn hãy để ý cái modulus $n^3$ và base $n + 1$. Định lý nhị thức:
\begin{align}
(n + 1 )^{x} = \sum_{k=0}^{x} \dfrac{x!}{k!(x-k)!}n^k
\end{align}

$enc$ đã bị mod đi $m^3$ tức là tất cả hệ số nhân với n mũ lớn hơn $2$ là không cần quan tâm.
\begin{align}
enc &\equiv (n + 1 )^{flag} \pmod{n^3} \\
&\equiv {}_{flag} C_2*n^2 + flag*n + 1 \pmod{n^3}
\end{align}
Vì vế phải của đẳng thức trên nhỏ hơn $n^3$ do đó ta có thể dễ dàng tìm dc flag bằng công thức sau:
$$
enc \equiv flag*n + 1 \pmod{n^2} \\
=> flag = \frac{enc - 1}{n}
$$

> **`ASIS{8!N0miaL_3XpAn5iOn_Us4G3_1N_cRyp7o_9rApHy!}`**

## Mindseat - Cryptohraphy - 66 solves

### Description
> PCryptography Mindset: Be Unpredictable, build robust and stable applications where you'll handle every situation that user can face or predict.
### Attachments
- mindseat_updated.py

#!/usr/bin/env python3

from Crypto.Util.number import *
from secret import params, flag

def keygen(nbit, k): # Pubkey function
	_p = 1
	while True:
		p, q = [_p + (getRandomNBitInteger(nbit - k) << k) for _ in '01']
		if isPrime(p) and isPrime(q):
			while True:
				s = getRandomRange(2, p * q)
				if pow(s, (p - 1) // 2, p) * pow(s, (q - 1) // 2, q) == (p - 1) * (q - 1):
					pubkey = p * q, s
					return pubkey

def encrypt(pubkey, m):
	n, s = pubkey
	r = getRandomRange(2, n)
	return pow(s, m, n) * pow(r, 2 ** k, n) % n

flag = flag.lstrip(b'ASIS{').rstrip(b'}')
nbit, k = params
PUBKEYS = [keygen(nbit, k) for _ in range(4)]
flag = [bytes_to_long(flag[i*8:i*8 + 8]) for i in range(4)]
ENCS = [encrypt(PUBKEYS[_], flag[_]) for _ in range(4)]

print(f'PUBKEYS = {PUBKEYS}')
print(f'ENCS = {ENCS}')

- output_updated.txt

PUBKEYS = [(10342840547250370454282840290754052390564265157174829726645242904324433774727630591803186632486959590968595230902808369991240437077297674551123187830095873, 5179654005441544601140101875149402241567866059199512232495766031194848985776186595289740052214499657697650832860279375151687044465018028876445070588827777), (6015512135462554031390611730578383462516861987731833360559070749140159284050335604168414434218196369921956160353365713819898567416920672209509202941444097, 2116441415129068001049624780654272734931672052541246678702416144768611225693039503554945326959705314527114860312641379671935648337975482830939466425225421), (6396980904648302374999086102690071222661654639262566535518341836426544747072554109709902085144158785649143907600058913175220229111171441332366557866622977, 1760317994074087854211747561546045780795134924237097786412713825282874589650448491771874326890983429137451463523250670379970999252639812107914977960011738), (9158217300815233129401608406766983222991414185115152402477702381950519098200234724856258589693986849049556254969769863821366592458050807400542885348638721, 6564146847894132872802575925374338252984765675686108816080170162797938388434600448954826704720292576935713424103133182090390089661059813982670332877677256)]
ENCS = [4595268033054096192076432659360373235610019564489694608733743330870893803828258295069937060360520598446948290913045781945314108935153236291467160667601985, 3390637292181370684803039833768819598968576813582112632809296088618666221278429695211004046274005776653775480723833818255766663573061866194380012311184611, 5197599582013327040903216369733466147938613487439777125659892779696104407398257678982801768761973934713675657188014051286238194316997970299887749668838196, 5093835186720390391696398671365109925058893544530286148616117890366909889206952477053316867658405460457795493886317792695055944930027477761411273933822112]

Bài này nặng kiến thức về Toán hơn. Bài sẽ chia flag thành 4 phần, mỗi phần 8 bytes và mỗi phần mã hóa bằng 1 pubkey khác nhau. Như vậy ta chỉ cần giải được 1 phần thì 3 phần còn lại tương tự

Để ý chỗ tạo `key` 1 xíu, ta thấy 2 số nguyên tố được tạo sẽ có dạng: $prime = 2^k*random + 1$, $p$ sẽ khoảng $nbit$, $random$ sẽ khoảng $nbit-k$ bit. `PUBKEYS` sẽ là 1 số $n = p * q$ và 1 số $s$ là căn nguyên thủy trên $\mathbb{Z}_{p}$. Từ `PUBKEYS` nhìn vào dạng binary của từng số ta có thể dễ dàng tìm dc $nbit=256$ và $k=134$

Plaintext $m$ sẽ bị mã hóa với 1 số $r$ được sinh ngẫu nhiên như sau:
$$enc \equiv s^{m}*r^{k} \pmod{n}$$

Chưa bàn tới việc mã hóa thì việc đầu tiên cần làm là factor được $n$. Các bạn có thể hiểu đơn giản việc nhân với 1 số là thừa của 2 giống như việc bạn dịch bit của số đó sang trái vậy (ví dụ: $11_2=1011, (11*2^4)_2=10110000$). Tương tự cái n sẽ có dạng:
$$
n = pq = (2^k*a+1)(2^k*b + 1) = 4^k*a*b+2^ka+2^kb+1 \\
\text{mà:} \ \ 2^ka + 2^kb < 4^k*a*b;\ \forall \ a, b > 2.
$$

Do đó có thể nói t chỉ cần xét toàn bộ $2*k$ bit đầu tiên của $n$ thành $0$ thì ta sẽ có $4^k*a*b=(p-1)(q-1)=phi$. Từ $phi$ và $n$, ta có thể factor thành thừa số nguyên tố bằng định lý Vi-Ét đảo:

def recover_primes(n):
    phi = ((n - 1) >> (2*k)) << (2*k)
    P = n
    S = n - phi + 1
    delta, check = iroot(S**2 - 4*P, 2)
    assert check
    x1 = (S + delta)//2
    x2 = (S - delta)//2
    return x1, x2

Việc factor $n$ đã xong, tiếp đến là giải mã `ciphertext`, `m` cần tìm là số mũ do đó đây là 1 bài toán liên quan đến `discrete log` nhưng ta không thể tìm thẳng vì vướng thằng $r$.

Đơn giản là chỉ cần làm thằng $r$ biến mất là được và việc đó lại rất dễ dàng khi $r$ đã được mũ với $2^k$.

\begin{align}
enc &\equiv s^mr^{2^k}\pmod{p} \\
\Leftrightarrow enc^a &\equiv (s^mr^{2^k})^a \pmod{p} \\
\Leftrightarrow enc^a &\equiv (s^a)^mr^{2^k*a} \pmod{p} \\
\Leftrightarrow enc^a &\equiv (s^a)^mr^{p-1} \pmod{p} \\
\Leftrightarrow \_enc &\equiv \_s^m \pmod{p} \\
\end{align}

Lý do mình dùng mod $p$ là vì `discrete log` trên trường hữu hạn dễ tính hơn, ngoài ra *m* cũng bé (khoảng 64 bits so với 134 bits của $k$) nên chỉ cẩn tìm trên $\mathbb{Z}_p$ là đủ để recover được $m$. Tính $m$:

def decrypt(c, s, p, q):
    Fp = GF(p)
    a = (p - 1)//(2 ^ k)
    _h = Fp(c) ^ a
    _g = Fp(s) ^ a
    x = discrete_log(_h, _g)
    return long_to_bytes(int(x))

Vì ta đã lũy thừa $s$ thêm $a$ lần trước do đó việc tính dlog trên sub-group $2^k$ được coi là trong thời gian đa thức (Thuật toán các bạn có thể tra trên mạng). Tìm **`FLAG`**:

flag = b"ASCIS{"
for enc, pubkey in zip(ENCS, PUBKEYS):
    n, s = pubkey
    p, q = recover_primes(n)
    flag += decrypt(enc, s, p, q)
flag += b"}"
print(flag.decode('utf-8'))

> **`ASCIS{N3w_CTF_nEW_Joye_Libert_CrYpt0_5}`**