A Brief Introduction to Cryptography in CTF Games

# A Brief Introduction to Cryptography in CTF Games

Chenghao Chen | 2023.6

Shanghai University

## Outline?!

<br>

1. 密码和编码
2. 古典密码学
3. 对称密码学
4. Hash 函数
5. 近世代数和数论
6. 非对称密码
7. 范畴论和同态加密
8. 格论和格密码

## Outline

1. 密码和编码
2. 近世代数和数论
3. 非对称密码-RSA
5. Challenges

# L1. 密码和编码

实际上是一个引言，并且介绍了 ancient 神必编码

## 1.1 一些会被搞混的术语

- 密码（Cryptography）：用于保护信息安全的过程
  - `Encrypt(k, m)`
  - `Decrypt(k, c)`
- 编码（Code Theory）：信息转换为不同形式的过程
  - `Encode(m)`
  - `Decode(e)`
- 口令（Password）：用户登录的凭证
- 散列（Hash）：（抗碰撞的）单向的压缩函数

## 1.2 常见编码方法

实用编码方法：

- 字符编码：ASCII, Unicode
- 二进制数据编码：base, Hex
- URL编码：e.g. `' '` -> `%20`

玩具编码方法：
- 与佛论禅：e.g. 佛曰：俱利知曳罰陀那無呐諦梵多不僧室得諳有呐跋姪阿
- 兽音译者：e.g. ~呜嗷呜呜呜呜~啊啊啊啊

## 1.2.1 字符编码转换错误

（一种比较古老的题目）
- 古早的时候编码标准不统一，会产生乱码
- GBK, BIG5, UTF-8
- e.g.:
  - （打开编码 UTF-8）��ѽѽѽѽѽѽ
  - （实际编码GBK）哇呀呀呀呀呀呀

## 1.2.2 锟斤拷

- Replacement Character �

🤔 锟斤拷
```python
> '�'.encode('utf-8')
b'\xef\xbf\xbd'
> '锟斤拷'.encode('gbk')
b'\xef\xbf\xbd\xef\xbf\xbd'
```

- 🤷随着文本替换，信息丢失

## 1.2.3 base64

base64

- 二进制-文本间的编码方法
- 64个编码字符（`'A-Za-z0-9+/'`）
- $64 = 2^6$，因而 base64 编码的码字可以表示6个bit的信息
- （[编码表](https://c.runoob.com/front-end/693/)）

🤔1个ASCII编码字符 8 bit，base64 一个码字 6 bit

如何编码？

## 1.2.4 base64 padding

- padding rule: `'0'`字符填充

```python
@Utils.print_params
def encode_b64_with_ascii_bin(text: str):
    binary_text  = ' '.join(format(ord(char), '08b') for char in text)
    encoded_text = base64.b64encode(text.encode('ascii'))
    return binary_text, encoded_text
```

```python
>>> encode_b64_with_ascii_bin('1')
Result: ('00110001', b'MQ==')

>>> encode_b64_with_ascii_bin('12')
Result: ('00110001 00110010', b'MTI=')

>>> encode_b64_with_ascii_bin('123')
Result: ('00110001 00110010 00110011', b'MTIz')
```

## 1.2.4 base64 padding (Cont'd)

```markdown
00110001
001100 01
001100 010000
MQ==
```

```markdown
00110001 00110010
001100 010011 0010
001100 010011 001000
MTI=
```

- 发现等号可以考虑base64解码

## 1.3 哈希函数

- 典：

- 哈希不是加密
- 虽然网上很多在线哈希都是加密（[例子](https://www.sojson.com/md5/)）

## 1.4 彩虹表

# L2. 近世代数和数论

中科院少年班招生要求：手撕大素数分解

## 2.1 数论

- 整除
- 素数和互素
- 算数基本定理
  - $N = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$
- 最大公约数（Greatest Common Divisor, GCD）
  - Euclidean 算法
  - 扩展 Euclidean 算法
    - $ax + by = \mathrm{gcd}(x, y)$
    - $ax + by = 1 \Rightarrow ax = -by + 1$
    - $\Rightarrow ax \equiv 1 (\bmod y)$   （$\mathbb{F}_p$上自然成立）

## 2.2 模运算算数性质

- let $[\cdot]$ denotes $(\cdot) \bmod n$
- $[[a]] = [a]$
- $[a] + [b] = [a+b]$
- $[a] - [b] = [a-b]$
- $[a \times b] = [[a] \times [b]]$
- $[a^k] = [[a]^k]$

## 2.3 更多知识

- Fermat 小定理
- Euler 函数
- 中国剩余定理
- 连分数
- ……

# L3. 非对称密码学

textbook RSA，但不会

## 3.1 非对称密码学基础

- 安全的单向陷门函数
- 利用Hash的构造……

- ↑ 在CTF中不是很重要

关注点：
- 选取素数的算数特性
- 不合理的加密指数、解密指数选取
- 不合理的加密方案修改

## 3.2 textbook RSA

```python
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from gmpy2 import invert

p = getPrime(128)
q = getPrime(128)

n = p * q
phi_n = (p - 1) * (q - 1)

e = 65537
d = invert(e, phi_n)

m = bytes_to_long(b'Hello, world!')
c = pow(m, e, n)
print(long_to_bytes(c))
m_ = pow(c, d, n)
print(long_to_bytes(m_))
```

## 3.2 textbook RSA (Cont'd)

```python
n = p * q
phi_n = (p - 1) * (q - 1)
```

- Euler 函数：小于等于$n$的与$n$互素的正整数的个数
- $\varphi(n) = \varphi(pq) = \varphi(p) \varphi(q) = (p-1)(q-1)$

```python
c = pow(m, e, n)
m_ = pow(c, d, n)
```

- $(m^e \bmod n)^d \bmod n = m^{ed} \bmod n$
- $ed = 1 \bmod \varphi(n)\Rightarrow ed = 1 + k\varphi(n)$
- $m^{ed} \bmod n = m^{1+k\varphi(n)} \bmod n$

## 3.2 textbook RSA (Cont'd)

- $m^{ed} \bmod n = m^{1+k\varphi(n)} \bmod n$
- $= (m \bmod n)(m^{k\varphi(n)} \bmod n) $
- $= (m \bmod n)(m^{\varphi(n)} \bmod n)^k \bmod n $

Euler 定理：若$m$ 和$n$ 互素，则$m^{\varphi(n)}\equiv 1 (\bmod n)$

- $n = pq, m < p, m < q$

- $m^{ed} \bmod n = (m \bmod n) (1)^k \bmod n$
- $= m \bmod n$

## 3.3 N 分解攻击

一种显然的攻击方法

- 小p, q
  - 因式分解
- p, q 差值太小或太大
  - Fermat, Pollard Rho 方法分解

工具：

- [yafu](https://sourceforge.net/projects/yafu/)
- [Integer factorization calculator](https://www.alpertron.com.ar/ECM.HTM)

## 3.3.1 Example 1 - Factor

```python
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

p = getPrime(128); q = getPrime(128)
n = p * q; phi_n = (p - 1) * (q - 1)
e = 65537

m = bytes_to_long(flag)
c = pow(m, e, n)

print(e); print(n); print(c)

# 65537
# 60312637199635801058227385421553206347253918440828187249920737695124886809487
# 14673748133379805475254231366717984351237192567008318062632171353909225806981
```

## 3.3.2 Example 1 try

- 浅浅分解一下

- 3分钟出结果

## 3.3.3 Example 1 poc

```python
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from gmpy2 import invert

e = 65537
n = 60312637199635801058227385421553206347253918440828187249920737695124886809487
c = 14673748133379805475254231366717984351237192567008318062632171353909225806981

p = 197_171715_027747_339553_722339_715394_949697
q = 305_888890_762796_266901_267235_667077_573071

phi_n = (p - 1) * (q - 1)

d = invert(e, phi_n)

m = pow(c, d, n)

print(long_to_bytes(m)) # b'flag{waaaaa!}'
```

## 3.4 小加密指数攻击

- 加密指数极小时，发生相关攻击（如$e=3$）
- 此时：
  - $c \equiv m^3(\bmod n)$
  - $m^3 = c + kn$
  - $m = (c+kn)^{1/3}$

攻击方法：Brute-force $k$

## 3.4.1 Example 2 - Low-Enc-Exp

```python
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from gmpy2 import invert
from secret import flag

p = getPrime(1024); q = getPrime(1024)

n = p * q
phi_n = (p - 1) * (q - 1)

e = 3

m = bytes_to_long(flag)
c = pow(m, e, n)

print(n) # 26904410424513850825570476100349039892015194282487533873593315635034916011599061467392303815306522302238291633926964464814719214360401710146660376698471334910919067631926359580676153648632072950953163800307452838629641502897202385008108650370210545081025594811346683868462241559023145711983469942804412184091372375410284776347467254451154229882893062676381167273759770532779269018405250741326382414128740659109901734318180074363144722523208937640098203271310259652100969148051051093951864097917984729026851490884006661280087277384483099665162338506927680335934552565079554069982479529726554065109787187999302935991923
print(c) # 31850476042869993856571693940454371912053546150176657900652418191965217904787395659877
```

## 3.4.2 Example 2 poc

```python
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from gmpy2 import invert, iroot

e = 3
n = 26904410424513850825570476100349039892015194282487533873593315635034916011599061467392303815306522302238291633926964464814719214360401710146660376698471334910919067631926359580676153648632072950953163800307452838629641502897202385008108650370210545081025594811346683868462241559023145711983469942804412184091372375410284776347467254451154229882893062676381167273759770532779269018405250741326382414128740659109901734318180074363144722523208937640098203271310259652100969148051051093951864097917984729026851490884006661280087277384483099665162338506927680335934552565079554069982479529726554065109787187999302935991923
c = 31850476042869993856571693940454371912053546150176657900652418191965217904787395659877

i = 0
while True:
    res = iroot(c+i*n, 3)
    if (res[1] == True):
        m = res[0]
        break
    print(f'\r i = {i}', end='')
    i += 1

print(long_to_bytes(m)) # b'flag{yeahh!}'
```

## 3.5 共模攻击

- 为什么 $n$ 每次都要重新生成？
- 假设重复利用 $n$

- $m^{e_1}\equiv c_1(\bmod n)$
  - $m^{e_2}\equiv c_2(\bmod n)$

- 攻击利用扩展 Euclidean算法（$ae_1+be_2\equiv1 (\bmod n)$）
  - 此时$m^{ae_1+be_2} = c_1^{a}c_2^{b} \bmod n$

## 3.5.1 Example 3 - Mod Share

```python
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from gmpy2 import invert
from secret import flag

p = getPrime(1024); q = getPrime(1024)
n = p * q; phi_n = (p - 1) * (q - 1)

e1 = getPrime(64); e2 = getPrime(64)

m = bytes_to_long(flag)
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

print(n)  # 15170797923892054990521305052012509493080568087081023750033741867542316768999951573646413753990834682138025772136109204509899638782616660243658254139599441045875522966283555995043016187825383943336990507193641549144516174056706810327582160942467845635495500282175716057977476074952304306822781341844677001797438535701007875365722512160465708455832225273446521621543823855283418665848061608565467010656663089973001969597624553258295614154262448569387247406903093192587512853122780974388687415079948784446715412138463084264315211437439421528085827503277507203193141860916227982534613135645331857382065795066181077972687
print(e1) # 9576072468337167131
print(e2) # 14939113163917820627
print(c1) # 2513254454937818539320001229715025367247490957880668052989469295768681316833496719591412918630312453676811713071414028525870397074185767769616621123070069290764497635067026772298781749325373581840750494743329569059911576372085939972798876709058137797441729480657418587957036217376669515209286767084322875440709473172117549721159755662718590954657925357615152141194701388245440956597032994743626281679318033304014413523468865879100948882376690862202243813943679264465530741774092309002963261692618613612757084511814696332961571153968794051052454203918248339932068292297123047852899029619284314623645966095118119009347
print(c2) # 111884194864476659139117439739496481475155670608279036093048194153438641356919888323493937575276768933859172174857427366301659912545016807339447507119749910478246208487569012877733924932126136220607107687643614867740936831894203006503190514539481184016080767542829000468460046831987529804871513461035761669072519101709086162745537847204230913330316446448321633091235409913844098851446548290633634428674269538902219278990312260703412892258533797387149328008600614619162876396153768090553946757954666629947494973412821804101257176286021758524844324847062425088549302146311886502815379004832574784487510491117203079999

```

## 3.5.2 Example 3 poc

```python
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from gmpy2 import invert, gcdext

n = 15170797923892054990521305052012509493080568087081023750033741867542316768999951573646413753990834682138025772136109204509899638782616660243658254139599441045875522966283555995043016187825383943336990507193641549144516174056706810327582160942467845635495500282175716057977476074952304306822781341844677001797438535701007875365722512160465708455832225273446521621543823855283418665848061608565467010656663089973001969597624553258295614154262448569387247406903093192587512853122780974388687415079948784446715412138463084264315211437439421528085827503277507203193141860916227982534613135645331857382065795066181077972687
e1 = 9576072468337167131
e2 = 14939113163917820627
c1 = 2513254454937818539320001229715025367247490957880668052989469295768681316833496719591412918630312453676811713071414028525870397074185767769616621123070069290764497635067026772298781749325373581840750494743329569059911576372085939972798876709058137797441729480657418587957036217376669515209286767084322875440709473172117549721159755662718590954657925357615152141194701388245440956597032994743626281679318033304014413523468865879100948882376690862202243813943679264465530741774092309002963261692618613612757084511814696332961571153968794051052454203918248339932068292297123047852899029619284314623645966095118119009347
c2 = 111884194864476659139117439739496481475155670608279036093048194153438641356919888323493937575276768933859172174857427366301659912545016807339447507119749910478246208487569012877733924932126136220607107687643614867740936831894203006503190514539481184016080767542829000468460046831987529804871513461035761669072519101709086162745537847204230913330316446448321633091235409913844098851446548290633634428674269538902219278990312260703412892258533797387149328008600614619162876396153768090553946757954666629947494973412821804101257176286021758524844324847062425088549302146311886502815379004832574784487510491117203079999

gcd, a, b = gcdext(e1, e2)

m = pow(c1, a, n) * pow(c2, b, n) % n

print(long_to_bytes(m)) # b'flag{zzZzzz}'
```

# Challenge

上强度

## Chal1. 套娃

- 本题共有3个flag
- 所有flag的形式均为`'flag{[0-9A-Za-z=_]*}'`

```
新佛曰：諸隸僧降冥吽諸陀摩隸僧缽冥薩願耨咤陀
願羅咤喃迦祗蜜耨阿嚤僧喼所聞薩闍嚩聞念須亦心
耨冥心阿冥聞慧蜜咤冥心念訶冥嚩冥聞冥念降咤冥
劫耨降寂願慧般祗闍隸冥修阿闍莊陀冥莊冥劫莊嚴
冥宣隸阿摩嚩蜜心咒冥闍我須咒慧冥闍諦羅迦聞慧
婆劫嘚慧咒迦慧慧我慧冥闍念劫嘇隸蜜祗伏嚤慧咒
修缽聞色祗冥闍僧嘚迦降阿莊冥慧聞蜜降咤寂波嘇
塞薩如囑
```

## Chal2. ezRSA

- 本题仅1个flag
- flag的形式均为`'flag{[0-9A-Za-z=_]*}'`

```python
from Crypto.Util.number import getPrime, bytes_to_long
from gmpy2 import is_prime, invert
from typing import Tuple
from secert import flag

def gen_rsa_param() -> Tuple[int, int, int, int, int]: ...
def rsa_encrypt(m: str, *args) -> str: ...

params = gen_rsa_param()
print(rsa_encrypt(flag, *params))
print(params[2])
# 5796768148637887491255587039409951397511832995737366433505141785703232675749200657380232851343254281355390391562734825283953711907092653161783752372166386
# 7948512242985881433771203281939490726039994357587772712416312873824297606161653053722572268861029945737411249803561023517431875922105282741637330609169129
```

</div>