← Notedeck
All engines
·
密码学
en
zh-CN
zh-TW
ja
ko
fr
de
es
pt-BR
tr
it
ar
密码学
12
engines
Extended Euclidean · gcd, Bézout & modular inverse
Extended Euclidean · gcd, Bézout & modular inverse
gcd+Bézout系数 as+bt=gcd · 回代 · 模逆元
Find gcd(a,b) and integers s,t with a·s + b·t = gcd(a,b); when gcd = 1 read off a⁻¹ mod b
Chinese Remainder Theorem · reconstruct x
Chinese Remainder Theorem · reconstruct x
互素模同余组 · Mᵢ·(Mᵢ⁻¹) · 唯一重构x
Solve x ≡ rᵢ (mod mᵢ) for pairwise-coprime moduli; the solution is unique mod M = ∏mᵢ
Euler's totient φ(n)
Euler's totient φ(n)
φ(n)=n∏(1−1/p) · 质因数分解 · 单位元计数
Count the integers in 1..n that are coprime to n via the prime-factor product formula
Miller–Rabin primality test
Miller–Rabin primality test
n−1=2^r·d · 见证平方序列 · 强伪证/合数
n−1 = 2^r·d, then a^d, a^(2d), … mod n — witnesses expose composites
Fermat's little theorem
Fermat's little theorem
a^(p−1)≡1 mod p · 幂序列 · 伪素数/Carmichael
a^(p−1) ≡ 1 (mod p) for prime p with gcd(a,p)=1
The birthday attack
The birthday attack
碰撞概率1−∏(1−k/N) · ≈√N · 哈希碰撞
P(collision) = 1 − ∏ (1 − i/N) crosses 50% near 1.177·√N
Elliptic-curve point addition
Elliptic-curve point addition
y²=x³+ax+b · 弦切法/F_p点加 · 斜率λ
The chord-and-tangent group law on y² = x³ + ax + b · over ℝ and over F_p
ElGamal public-key encryption
ElGamal public-key encryption
h=g^x · c1=g^k,c2=m·h^k · 解密还原m
Encrypt over Z_p* · keygen h=gˣ, encrypt (gᵏ, m·hᵏ), decrypt m = c₂·(c₁ˣ)⁻¹
Shamir's Secret Sharing (t, n)
Shamir's Secret Sharing (t, n)
(t,n)门限 · 多项式f(0)=S · Lagrange重构
Split a secret into n shares · any t reconstruct it, any t−1 reveal nothing
Feistel network · encrypt / decrypt
Feistel network · encrypt / decrypt
L/R交换异或 · 轮函数F · 加解密对称还原
Swap-and-XOR rounds that reverse to recover the plaintext exactly
One-time pad · XOR secrecy & key reuse
One-time pad · XOR secrecy & key reuse
c=m⊕k · 完美保密 · 密钥重用c1⊕c2泄露
c = m ⊕ k is perfectly secret used once — and leaks m₁⊕m₂ if the key repeats
Merkle tree · inclusion proof
Merkle tree · inclusion proof
哈希树 · 包含证明审计路径 · 重算到根验证
Hash pairs up to a root; prove one leaf with an audit path; tampering breaks it