A Brief Introduction to Cryptography in CTF Games

Chenghao Chen | 2022.6

Shanghai University

Outline?!


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

Outline



  1. 密码和编码
  2. 近世代数和数论
  3. 非对称密码-RSA
  4. 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 �

🤔 锟斤拷

> '�'.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的信息
  • （编码表）

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

如何编码？

1.2.4 base64 padding

  • padding rule: '0'字符填充
@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

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

00110001
001100 01
001100 010000
MQ==

00110001 00110010
001100 010011 0010
001100 010011 001000
MTI=
  • 发现等号可以考虑base64解码

1.3 哈希函数

  • 典：

  • 哈希不是加密
  • 虽然网上很多在线哈希都是加密（例子）

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

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)

n = p * q
phi_n = (p - 1) * (q - 1)
  • Euler 函数：小于等于$n$的与$n$互素的正整数的个数
  • $\varphi(n) = \varphi(pq) = \varphi(p) \varphi(q) = (p-1)(q-1)$
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 方法分解

工具：

3.3.1 Example 1 - Factor

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

  • 浅浅分解一下

center

  • 3分钟出结果

3.3.3 Example 1 poc

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

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

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

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

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

3.6 More Exercise 1

n=111579281253062835933426384911624147476643761873859056052262953708472502295896995336206948247132120107672205900512683609160859648751240065855474276219994138942756004010593263891617114133265991974868701112328627021663637323794664244913574481420588357101626589818721266368311914527609221633764177929512932572431
c=88870500129800281970105647465034249962408043895876390636948381637648563368839286409491487914616157808689098599152353765340352358559100732226540197353569675894540877184980032542071641988321773490955995436271805369857124988164094166523947397743529988209384145974211768757896487704118410946032129361588104389830
e=65537

3.6.1 poc

import gmpy2
from sympy import nextprime
from Crypto.Util.number import *
n=111579281253062835933426384911624147476643761873859056052262953708472502295896995336206948247132120107672205900512683609160859648751240065855474276219994138942756004010593263891617114133265991974868701112328627021663637323794664244913574481420588357101626589818721266368311914527609221633764177929512932572431
c=88870500129800281970105647465034249962408043895876390636948381637648563368839286409491487914616157808689098599152353765340352358559100732226540197353569675894540877184980032542071641988321773490955995436271805369857124988164094166523947397743529988209384145974211768757896487704118410946032129361588104389830
e=65537
q=nextprime(gmpy2.iroot(n,2)[0])
p=n//q
d=gmpy2.invert(e,(p-1)*(q-1))
m=pow(c,d,n)
print(long_to_bytes(m))
#flag{llsajdjlksajldjsdjkl}

3.7 Wiener’s RSA Attack

  • 小解密指数攻击（$d<1/3n^{1/4}$）
  • 连分数
    • $x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{\ddots,}}}} $
    • $x = [a_0, a_1, a_2, \cdots]$

3.7 Wiener’s RSA Attack (Cont’d)

  • $ed = 1 + k\varphi(N)$
  • $\left| \frac{e}{\varphi(N)} - \frac{k}{d}\right| = \frac{1}{d\varphi(N)}$
  • 若$N$足够大，则$k/d$是对$e/\varphi(N)$ 的估计
  • 敌手只有$e$和$N$，但是$\varphi(N) \approx N$

Wiener’s Theorem

  • $k/d$ 可以在多项式时间内从$e/N$的连分数中找到
  • 测试$k’, d’$，若$(ed-1) \bmod k = 0$

3.7.1 More Exercise 2

RSA:
n=56661243519426563299920058134092862370737397949947210394843021856477420959615132553610830104961645574615005956183703191006421508461009698780382360943562001485153455401650697532951591191737164547520951628336941289873198979641173541232117518791706826699650307105202062429672725308809988269372149027026719779368169
e=36269788044703267426177340992826172140174404390577736281478891381612294207666891529019937732720246602062358244751177942289155662197410594434293004130952671354973700999803850153697545606312859272554835232089533366743867361181786472126124169787094837977468259794816050397735724313560434944684790818009385459207329
c=137954301101369152742229874240507191901061563449586247819350394387527789763579249250710679911626270895090455502283455665178389917777053863730286065809459077858674885530015624798882224173066151402222862023045940035652321621761390317038440821354117827990307003831352154618952447402389360183594248381165728338233

BASE:
"GHI45FQRSCX****UVWJK67DELMNOPAB3"

Challenge

上强度

Chal1. 套娃

  • 本题共有3个flag
  • 所有flag的形式均为'flag{[0-9A-Za-z=_]*}'
新佛曰：諸隸僧降冥吽諸陀摩隸僧缽冥薩願耨咤陀
願羅咤喃迦祗蜜耨阿嚤僧喼所聞薩闍嚩聞念須亦心
耨冥心阿冥聞慧蜜咤冥心念訶冥嚩冥聞冥念降咤冥
劫耨降寂願慧般祗闍隸冥修阿闍莊陀冥莊冥劫莊嚴
冥宣隸阿摩嚩蜜心咒冥闍我須咒慧冥闍諦羅迦聞慧
婆劫嘚慧咒迦慧慧我慧冥闍念劫嘇隸蜜祗伏嚤慧咒
修缽聞色祗冥闍僧嘚迦降阿莊冥慧聞蜜降咤寂波嘇
塞薩如囑

Chal2. ezRSA

  • 本题仅1个flag
  • flag的形式均为'flag{[0-9A-Za-z=_]*}'
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