PV181 Laboratory of security
and applied cryptography
Asymmetric cryptography
Marek Sýs, Zdeněk Říha
| PV1811
Asymmetric cryptography
• Confidentiality
– asymmetric cipher - encryption, key agreement
• Authentication
1. Entity – identity verification – certificates,
2. Data origin - digital signature
• Integrity
– digital signature
• Non-repudiation
– digital signature
2 | PV181
Asymmetric cryptosystem
3 | PV181
Adapted Source: Network and
Internetwork Security (Stallings)
encryption decryption
message
Alice
Public key of Bob
Bob
Private key of Bob
Encrypted
message
Decrypted
original
message
Asymmetric cryptography
• Two related keys – created by one party
– different inverse operations (encryption - decryption, signing
– signature verification)
• Properties - hard to compute private from public key
– based on hard mathematical problems
• Hard problems and cryptosystems:
– Integer factorization – RSA, Rabin, …
– Discrete logarithm problem (DLP): ElGamal, EC, DSA, …
– Others (DH, decoding,…) – Diffie-Helman, McElliece,…
4 | PV181
Hard problems
• Integer factorization
– for N find its nontrivial divisor
• DLP in domains:
(parameters: define alg. structure and DLP)
– 𝑍 𝑝 defined by 𝑝 :
• for 𝑔, ℎ find 𝑥 such that 𝑔 𝑥
≡ ℎ 𝑚𝑜𝑑 𝑝
– Elliptic curve defined by triple 𝑎, 𝑏, 𝑝:
• for points 𝐺, 𝐻 find 𝑥 such that 𝑥. 𝐺 = 𝐻
5 | PV181
RSA generation
• Two random primes 𝑝, 𝑞
– 𝑝𝑟𝑖𝑚𝑒 − 1 must have large factor (110 bits)
• Public exponent 𝑒 chosen so:
– gcd 𝑝 − 1, 𝑒 = gcd 𝑞 − 1, 𝑒 = 1
– typically set 65537 – prime number
– very small 𝑒 is insecure: e.g. 𝑒=3 sent to 3 recipients
• Private exponent 𝑑 computed
– from 𝑒 so that : 𝑒. 𝑑 ≡ 1 𝑚𝑜𝑑 𝑝 − 1 ∗ 𝑞 − 1
– Small 𝑑 is insecure – < 0.29*bits of N (𝑑 can be computed)
6 | PV181
RSA keys
• Public key
– 𝑁 = 𝑝. 𝑞 , 𝑒
• Private key
– 𝑑 but 𝑝, 𝑞 must be kept secret
• Encryption: 𝐸 𝑝 = 𝑚 𝑒
𝑚𝑜𝑑 𝑁
• Decryption: 𝐷 𝑐 = 𝑐 𝑑
𝑚𝑜𝑑 𝑁
– Can be sped up (4x) using CRT
• 𝐷 𝑐 = 𝑐 𝑑2 𝑚𝑜𝑑 𝑞 + C. ( 𝑐 𝑑1 𝑚𝑜𝑑 𝑝 − 𝑐 𝑑2 𝑚𝑜𝑑 𝑞),
for 𝑑2 = 𝑑 𝑚𝑜𝑑 𝑞 − 1, 𝑑1 = 𝑑 𝑚𝑜𝑑 𝑝 − 1
7 | PV181
RSA Padding example (PKCS#1 v1.5)
• Document
– “00 01 02 03 04 05 06 07 07 06 05 04 03 02 01”
• Hash of the document (sha-1)
– “b3 39 90 4c d2 a0 10 e6 19 37 eb e5 b5 83 37 8c 5d 10
51 95”
• Padded hash
– “00 01 ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff 00
30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 b3 39 90 4c
d2 a0 10 e6 19 37 eb e5 b5 83 37 8c 5d 10 51 95”
RSA in practice: Padding
• Non-random padding (textbook RSA) is insecure
- Bleichenbacher attack – oracle attack (information about
improper format of message) CCA
• Paddings - random value computed from message
– ANSI X9.31
– PKCS #1 v1.5
– Probabilistic Signature Scheme (PSS)
– OAEP – PKCS#1 v2 & RFC 2437- completely random -
secure
Diffie-Hellman (DH) algorithm
• Described in PKCS#1
• Params:
– 𝑝, 𝑔 prime, generator of subgroup in 𝑍 𝑝, define DLP 𝑔 𝑥 ≡ ℎ 𝑚𝑜𝑑 𝑝
• Private key: 𝑥
• Public key: 𝑔, 𝑝, ℎ (ℎ ≡ 𝑔 𝑥
𝑚𝑜𝑑 𝑝)
• Key agreement - both participants affect the key
– Alice sends: 𝑔 𝑎
𝑚𝑜𝑑 𝑝
– Bob sends: 𝑔 𝑏 𝑚𝑜𝑑 𝑝
– Shared key 𝑔 𝑎𝑏 𝑚𝑜𝑑 𝑝 computed as:
• (𝑔 𝑎 𝑚𝑜𝑑 𝑝) 𝑏 𝑚𝑜𝑑 𝑝 or (𝑔 𝑏 𝑚𝑜𝑑 𝑝) 𝑎 𝑚𝑜𝑑 𝑝
10 | PV181
Digital signature
• Asymmetric cryptography
– Private key – signature generation (usually only hash of
data is typically signed not data itself)
– Public key – verification procedure
• Data integrity + data origin + non-repudiation:
– Non-repudiation - correct signatures can be generated
only by those having the private key
• The digital signature itself does not give any
guarantees with respect to signing time.
Digital signature scheme
12 | PV181
Signature
algorithm
Verification
algorithmmessage signed
message
Alice
Public key of Alice
Bob
Source: Network and
Internetwork Security (Stallings)
verified
message
Private key of Alice
Digital Signature Algorithm (DSA)
• In 1994 the selection procedure for Digital Signature Standard
(DSS) was concluded – DSA (Digital Signature Algorithm) was
selected.
• Modified version of ElGamal algorithm, based on discrete
logarithm in Zp.
• Became FIPS standard FIPS 186 in 1993.
– Standards – 186-1, 186-2, 186-3, 186-4
– Now NIST FIPS 186-4 supports RSA & DSA & ECDSA.
Digital Signature Standard (DSS)
14 | PV181
DSS
1. Selection of Parameter Sizes and Hash Functions
2. Domain Parameter Generation
- only for DSA, ECDSA
3. Signature Generation
4. Signature Verification and Validation
15 | PV181
DSA: Key generation
• Parameter generation
– Key length: 𝑁, 𝐿 bits
1. Choose prime 𝑞 with 𝑁 bits
2. Choose prime modulus 𝑝 with 𝐿 bits such that: 𝑞|𝑝
3. Choose 𝑔 with order 𝑞 in 𝑍 𝑝
Keys:
• Private key: 𝑥
• Public key: 𝑝, 𝑔, 𝑞, ℎ (ℎ ≡ 𝑔 𝑥 𝑚𝑜𝑑 𝑝)
DSA signature generation & verification
• Signature generation
– Generate a random per-message value k such that 0 < k < q.
– Calculate r = (gk mod p) mod q
– Calculate s = (k−1(H(m) + x*r)) mod q
– The signature is (r, s).
• Signature verification
– w = (s)−1 mod q
– u1 = (H(m)*w) mod q
– u2 = (r*w) mod q
– v = ((gu1*yu2) mod p) mod q
– The signature is valid if v = r
• For DSA (1024,160) the signature size will be 2x160 bits.
DSA: Padding
• Decide on lengths L and N, e.g. (1024,160).
– N must be less than or equal to the hash output length
• E.g. for (1024,160) sha-1 is typically used,
sha-256 would be ok as well and only first 160 bits would be
used
– s = (k−1(H(m) + x*r)) mod q
• “It is recommended that the security strength of the (L, N) pair and the security strength of the hash
function used for the generation of digital signatures be the same unless an agreement has been
made between participating entities to use a stronger hash function. When the length of the output of
the hash function is greater than N (i.e., the bit length of q), then the leftmost N bits of the hash
function output block shall be used in any calculation using the hash function output during the
generation or verification of a digital signature. A hash function that provides a lower security
strength than the (L, N) pair ordinarily should not be used, since this would reduce the security
strength of the digital signature process to a level no greater than that provided by the hash
function.” [FIPS 186-3]
Elliptic curve DSA (ECDSA)
• Elliptic curves invented by Koblitz & Miller in 1985.
• ECDSA proposed in 1992 by Vanstone
• Became ISO standard (ISO 14888-3) in 1998
• Became ANSI standard (ANSI X9.62) in 1999
• ECDSA, ECDH is a version of DSA, DH based on
elliptic curves.
Elliptic curve (EC) domain parameters
• (field,a,b,G,n,h)
– Finite field
• p for Fp
• m, bases (trinomial, pentanomial) for F2
m
– Coefficients a, b: y2 = x3 + ax +b
– Group generator: G
– Order of the G: n
– Optional cofactor: h
• (h = number points of EC / order n)
– The base point G generates a cyclic subgroup of order n in
the field.
Elliptic curve DH (ECDH)
• Described in PKCS#1
• Params:
– 𝑝, 𝑎, 𝑏 define EC over 𝑍 𝑝
– generator of EC - point 𝑮, definess DLP: 𝑥𝑮 = 𝐻
• Private key: 𝑥
• Public key: 𝐺, 𝐸𝐶, 𝐻 (𝐻 = 𝑥. 𝐺)
• Key agreement - both participants affect the key
– Alice sends: 𝑎. 𝐺
– Bob sends: 𝑏. 𝐺
– Shared key 𝑎. 𝑏. 𝐺 computed as:
• 𝑏. (𝑎. 𝐺) or 𝑎. (𝑏. 𝐺)
ECDSA: Keys
• Generating key pair
– Select a random integer d from [1,n − 1]
– Compute P = d*G;
• Private key: d
• Public key: P
• For 256-bit curve
– the private key d will be approx. 256-bit long
– the public key P is a point on the curve – will be approx
512-bit long
ECDSA: Signatures
• Generate signature
– Select a random integer k from [1,n − 1]
– (x1,y1) = k*G
– Calculate r = x1 (mod n)
– Calculate s = k−1(M + r*d) (mod n)
– Signature is (r,s).
• Signature verification
– Calculate w = s−1 (mod n)
– Calculate u1 = z*w (mod n) & u2 = r*w (mod n)
– Calculate (x1,y1) = u1*G + u2*P
– The signature is valid if r = x1 (mod n).
• For 256-bit curve the signature length will be approx.
512 bits
ECDSA: Padding
• Rules are same as for DSA
• “It is recommended that the security strength associated with the bit length of
n and the security strength of the hash function be the same unless an
agreement has been made between participating entities to use a stronger
hash function. When the length of the output of the hash function is greater
than the bit length of n, then the leftmost n bits of the hash function output
block shall be used in any calculation using the hash function output during
the generation or verification of a digital signature. A hash function that
provides a lower security strength than the security strength associated with
the bit length of n ordinarily should not be used, since this would reduce the
security strength of the digital signature process to a level no greater than that
provided by the hash function.” [FIPS 186-3]