PV181 Laboratory of security
and applied cryptography
Public key crypto
Common math operations
Marek Sýs
syso@mail.muni.cz, A405
You will learn
• How to generate public/private key pair.
• Formats of cryptographic data
• Base64,
• ASN1 (PEM, DER)
• Mathematical operations used in public-key
cryptography
• Modular operations
• Operations with points on Elliptic curve
Public key operations
• Modular operations:
– Addition
– Multiplication
– Exponentiation
– Inversion (uses Extended Euclid alg.)
• Elliptic curve operations:
– Point addition
– Point multiplication (e.g. point doubling 2*P = P+P)
3
Modular operations
• The result always in [0, m-1] for modulus m
• Addition, multiplication: 𝑎 + 𝑏 𝑚𝑜𝑑 𝑚, 𝑎 ∗ 𝑏 𝑚𝑜𝑑 𝑚
– In python a+b % m, a*b % m
• Exponentiation: 𝑎 𝑒
𝑚𝑜𝑑 𝑚
– In python pow(a, e, m)
– Computed iteratively with modulo applied to decrease
size of intermediate products
– 𝑎11
𝑚𝑜𝑑 𝑚 ⇒ 11 = 1 + 2 + 8 ⇒ 𝑎11
= 𝑎1
∗ 𝑎2
∗ 𝑎8
• 𝑎1, 𝑎2 = 𝑎 ∗ 𝑎 𝑚𝑜𝑑 𝑚, 𝑎4 = 𝑎2 ∗ 𝑎2 𝑚𝑜𝑑 𝑚, 𝑎8 , 𝑎16
• 𝑎11 𝑚𝑜𝑑 𝑚 = 𝑎1 ∗ 𝑎2 𝑚𝑜𝑑 𝑚 ∗ 𝑎8 𝑚𝑜𝑑 𝑚
4
Modular inversion
• Inverse 𝑏−1 of 𝑏 modulo 𝑚
– 𝑏−1 such that 𝑏−1 ∗ 𝑏 = 𝑏 ∗ 𝑏−1 = 1 𝑚𝑜𝑑 𝑚
– 𝑏 and 𝑚 must be coprime!
• Modular “division” using inverse:
𝑎
𝑏
𝑚𝑜𝑑 𝑚 = 𝑎 ∗ 𝑏−1 𝑚𝑜𝑑 𝑚
– In python (a * pow(a, -1, m)) %
• Examples:
– 3−1 𝑚𝑜𝑑 7 = 5 since 3 ∗ 5 𝑚𝑜𝑑 7 = 1
– 4−1 𝑚𝑜𝑑 10 does not exist (gcd 4, 10 = 2 )
5
RSA
• Public 𝑁, 𝑒
– Encryption – modular exponentiation
• 𝐸 𝑚 = 𝑚 𝑒
𝑚𝑜𝑑 𝑁
• Private 𝑒, 𝑑, 𝑝, 𝑞, 𝑁
– Decryption – modular exponentiation
• 𝐷 𝑐 = 𝑐 𝑑
𝑚𝑜𝑑 𝑁
• Private
– Decryption – modular exponentiation using CRT
6
Elliptic curve cryptography (ECC)
• Defined by parameters
– 𝑎, 𝑏, 𝑝, 𝐺, 𝑞
• Groups of points (𝑥, 𝑦)
– 𝑦2
= 𝑥3
+ 𝑎𝑥 + 𝑏 𝑚𝑜𝑑 𝑝
• Operations with points:
– Addition - complex wiki 𝑥1, 𝑦1 + 𝑥2, 𝑦2 ≠ 𝑥3, 𝑦3
– Multiplication vs addition – classical relationship
• E.g. 3 ∗ 𝑥1, 𝑦1 = 𝑥1, 𝑦1 + 𝑥1, 𝑦1 + 𝑥1, 𝑦1
• Maximal multiplier 𝑞 i.e
– 𝑘 ∗ 𝑥1, 𝑦1 = 𝑘 𝑚𝑜𝑑 𝑞 ∗ 𝑥1, 𝑦1
7