2024 Crypto

# A Brief Introduction to Cryptography in Cybersecurity

Chenghao Chen | 2024.6

Shanghai University

## Outline

1. Before Lecture ...
2. 密码学介绍
3. 近世代数和数论基础
4. textbook RSA 相关攻击方法
5. Challenges

# 1. Before Lecture

What you should learn from this lecture?

## Cracked Bachelor Education

- 《上海交通大学生存手册》[click here](https://survivesjtu.gitbook.io/survivesjtumanual)
  - 各位同学们，在本书的开始，我不得不遗憾地告诉大家一个消息。国内绝大部分大学的本科教学，不是濒临崩溃，而是**早已崩溃**。在此，我无意争论是否复旦、中科大、或者清华、北大是否比我们崩溃的更少一些——这种争论是没有意义的。我只是看到了无数充满求知欲、激情、与年轻梦想的同学们，将要把自己的四年青春，充满希望与信任地交给大学来塑造。这使我心中非常不安。
- SHU?
    - Computer Security and Privacy
    - Information Security Techniques
    - (Elect) Security of IoTs
    - (Elect) Network Intrusion Detection

## 通用补充材料

- 学会提问：
  - [提问的智慧](https://github.com/ryanhanwu/How-To-Ask-Questions-The-Smart-Way/blob/main/README-zh_CN.md) / [别像弱智一样提问](https://github.com/tangx/Stop-Ask-Questions-The-Stupid-Ways/blob/master/README.md)
  - **STFW** - Search The Friendly Web
  - **RTFM** - Read The Friendly Manual
  - **RTFSC** - Read The Friendly Source Code
  - 你想要的答案很容易找到, 你很应该自己去获取
  - 相比于我直接告诉你答案, 你自己获取答案能学到更多
- 学会使用工具：
  - [计算机教育中缺失的一课](https://missing-semester-cn.github.io/)
  - Linux, Shell, Git, Vim

## 为什么要学习密码学？

密码学是保障信息安全的基石
- 2020年1月1日起施行《密码法》
- 2021年新增“密码科学与技术”本科专业

功利角度：
- 竞赛加分：
  - 全国大学生信息安全竞赛（A类）
  - 全国高校密码数学挑战赛（B类）
  - 全国大学生信息安全与对抗技术竞赛（B类）
- 读研深入学习：择校范围广泛
- 就业：密码学研究员、密码工程、密码测评...

## 为什么要学习密码学？(Cont'd)

毕业生去向：
  - 研究生项目
    - 网安（密码学, 网络, ...）
    - 其他（AI 方向）
  - 就业
    - 软件开发、安全服务、运维、测试
  
本 Lecture 希望各位同学能了解到密码学的**基本**概念

- L1. 密码学概念简要介绍
- L2. textbook RSA 攻击相关内容

# 2. 密码学介绍

从远古技艺到现代科学

## 易混淆概念解析

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

## 常见编码方法

实用编码方法：

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

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

## 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

如何编码？

## 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')
```

## base64 padding (Cont'd)

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

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

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

## Hash 函数

- 典：

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

## Hash 函数 (Cont'd)

Hash 函数具有以下特点：

```
hash(value: array<byte>) -> vector<byte, N>  (N对于该函数固定)
```

校验 examples:

```sh
$ printf 'hello' | sha1sum
aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d
$ printf 'hello' | sha1sum
aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d
$ printf 'Hello' | sha1sum 
f7ff9e8b7bb2e09b70935a5d785e0cc5d9d0abf0
```

- 抽象地讲，散列函数可以被认为是一个不可逆，且看上去随机，但具确定性的函数（如何理解看上去随机？）

## 凯撒密码

- 凯撒（Caesar）密码：已知最早的密码
- 用途：保密通信
- 凯撒密码加密时，会将原始信息（明文）中的每个字母，按照其在字母表中的顺序向后移动**固定数目**作为加密信息（密文）

```
明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表：DEFGHIJKLMNOPQRSTUVWXYZABC
```

形式化表达：
$$
cipher = plain + key \pmod{26}
$$

但容易被破解（穷尽搜索 $key$）

## 古典密码

- 替换和代换的技艺
  - 单表代换密码
    - 凯撒密码、移位密码、仿射密码
  - 多表代换密码
    - Vigenere 密码、Hill 密码

- 都已经被破解：穷尽搜索、词频分析...
- 不能满足更高的安全需求
  - 计算机出现，算力指数提升
  - 远古技艺全靠脑补，不可证明安全性

## 现代密码学

- 成为理论计算机科学的一大分支

## 现代密码学 (Cond't)

- 机密性、完整性、可用性要求
- 针对每个 bit 的分析，而非单纯的“我寻思能行”
- 基于数学的可证明安全体系

思考：如何形式化说明“看上去随机”？

- 典型的密码学小公式，计算不可区分：

$$
\left|
\Pr\left[
    D\left(
        X(a,n)
    \right)=1
\right]-
\Pr\left[
    D\left(
        Y(a,n)
    \right)=1
\right]
\right| \leq \mathrm{negl}(n)
$$

- $X, Y$ 是两个随机变量，$a$是输入值，$n$ 是安全参数
- $D$ 是一个多项式时间算法

## 现代密码学的用处

- 基础：密钥协商和安全通信
- 网络通信的安全 (SSL/TLS)
  - 握手协议：通过公钥密码学进行会话密钥协商
  - 记录层：使用共享的会话密钥传输数据
  - 以上过程确保数据的机密性和完整性
- 磁盘加密（BitLocker）
- 数字签名
- 匿名通信 -> 匿名交易 -> 区块链
- 安全选举投票
- 安全外包计算（隐私计算）

## 现代密码学研究领域

- 公钥密码学：密码分析、后量子密码学、量子公钥密码学
- 对称密码学：量子密码、Hash 函数、MAC、认证加密
- 密码学理论基础：安全假设、随机性、理想模型、下限证明
- 密码工程：软硬件实现、随机数发生器、物理攻击、侧信道攻击
- 高级密码原语：同态加密、安全多方计算、泛函加密、不可区分混淆、多线性映射、零知识证明、安全承诺、数字签名
- 现实世界的密码攻击和应用：区块链和加密货币、分布式算法

<br>

**今日话题**：公钥密码学 - 密码分析 - RSA密码分析入门

# 3. 近世代数和数论基础

你能手撕大素数分解吗？

## 数论

- 整除
- 素数和互素
- 算数基本定理
  - $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$上自然成立）

## 模运算算数性质

- $(a \bmod n) \bmod n = a \bmod n$
- $a \bmod n + b \bmod n = (a+b) \bmod n$
- $a \bmod n - b \bmod n = (a+b) \bmod n$
- $(ab) \bmod n = (a \bmod n)(b \bmod n) \bmod n$
- $(a^k)\bmod n = (a \bmod n)^k \bmod n$

## 更多知识

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

# 4. textbook RSA 相关攻击方法

textbook RSA，但不会

## 非对称密码学基础

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

- ↑ 在 CTF 中不是很重要

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

## 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_))
```

## 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$

## 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$

## N 分解攻击

一种显然的攻击方法

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

工具：

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

## 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
```

## Example 1 try

- 浅浅分解一下

- 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!}'
```

## 小加密指数攻击

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

攻击方法：Brute-force $k$

## 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
```

## 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!}'
```

## 共模攻击

- 为什么 $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$

## 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

```

## 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}'
```

# 5. 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>