PV181 Laboratory of security
and applied cryptography
Part 3, seminar 8:
Advanced Topics
Łukasz Chmielewski
chmiel@fi.muni.cz
| PV1811
Outline
• Finishing the last week’s exercises (10min)
– Optional task discussion
• Recall from the last seminars
– We concentrate on signatures
• RSA, RSA-CRT
• DSA, ECDSA
• Efficiency
• Post Quantum
2 | PV181
Finishing the last week’s exercises
• Anything before Task 6?
• Task 6 and 7…
• Email encryption – Assignment 7
3 | PV181
Tasks 6 & 7:
• Both are doable but mathematically not trivial for arbitrary e..
– For a complete solution see: Handbook of Applied Cryptography (chapter 8, section
8.2.2, page 287). Link: https://cacr.uwaterloo.ca/hac/
• However e is normally small: e=0x010001=65537
• Therefore, the following attack is possible for d, n, and e known:
1. We have eꞏd = kꞏ𝜑 𝑛 + 1 for some integer k. Since d < 𝜑 𝑛 , we know that k < e. So
you only have a small number of k to try to get 𝜑 𝑛 .
• Note that 𝜑 𝑛 ≈ 𝑛 or at least most significant bits.
• For small e: k'=round(ed/n). k' is very close to k (i.e. |k'-k| <= 1).
2. Given k, you easily get 𝜑 𝑛 = (ed-1)/k.
3. Now 𝜑 𝑛 = (p-1)(q-1) = n + 1 - (p+q). Thus, you get p+q = n + 1 - 𝜑 𝑛 .
• So we have p+q and n=pꞏq.
• Note that for all real numbers a and b, a and b are the two solutions of the
quadratic equation X2-(a+b)ꞏX+aꞏb=0.
4. Compute: …
4 | PV181
Tasks 6 & 7 cont’d
4. Compute:
• p = ((p+q) + (p+q)2 − 4ꞏpq) / 2
• q = ((p+q) - (p+q)2 − 4ꞏpq))/2
• Easier way, there is a function to compute p and q from (n,e,d):
– cryptography.hazmat.primitives.asymmetric.rsa.rsa_recover_prime_factors(n,e,d)
• For dp=d (mod p), n, and e known, the attack is easier:
– dp ≤ d < 𝜑 𝑛
– eꞏdp = 1 (mod (p-1)) and therefore eꞏdp = kꞏ(p-1)
– k<e so we can brute force k again and we compute x= eꞏdp + k = kꞏp
– Now we compute gcd(x,n) to obtain p.
• More to read:
– “Reconstructing RSA Private Keys from Random Key Bits”:
https://eprint.iacr.org/2008/510.pdf
– “Weaknesses in Current RSA Signature Schemes”:
https://link.springer.com/chapter/10.1007/978-3-642-31912-9_11
5 | PV181
encryption decryption
message
Alice
Public key of Bob
Bob
Adapted Source: Network and
Internetwork Security (Stallings)
Private key of Bob
Encrypted
message
Decrypted
original
message
| PV1816
Recall: Asymmetric cryptosystem
Digital signature scheme
7 | 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
• Alice generates key pair
– Public key is published (sent to Bob) for verification of
signature
• Alice sign a document using her private key
• Bob use public key to verify the digital signature
• Classical examples: RSA, ECC
• Post-Quantum Schemes:
– Why?
8 | PV181
RSA: reminder
1. Secret primes 𝑝, 𝑞: 𝑛 = 𝑝 ∙ 𝑞
2. Public exponent 𝑒:
gcd 𝑒, (𝑝 − 1) = gcd 𝑒, (𝑞 − 1) = 1
3. Private exponent 𝑑: 𝑑 ∙ 𝑒 ≡ 1 𝑚𝑜𝑑 𝜑 𝑛
Encryption (public 𝑛, 𝑒): 𝐸 𝑚 = 𝑚 𝑒 𝑚𝑜𝑑 𝑛 = 𝑐
Decryption (private 𝑛, 𝑑): 𝐷 𝑐 = 𝑐 𝑑 𝑚𝑜𝑑 𝑛 = 𝑚
9 | PV181
RSA-CRT: mathematics
• Optimization of computing a signature giving about 3 or 4-fold speed-up
• Precompute the following values:
– Find dp = d (mod p-1), computed as dp = e-1 (mod p-1)
– Find dq = d (mod q-1)
– Compute iq = q-1 (mod p)
• Computations using mp = m (mod p) and mq = m (mod q)
• Signature or encryption (forgetting about hashing):
– sp = 𝑚 𝑑 𝑝 (mod p)
– sq = 𝑚 𝑑 𝑞 (mod q)
– Garner’s method (1965) to recombine sp and sq:
• s = sq + q · (iq(sp − sq) (mod p))
11 | PV181
Discrete Logarithm Problem 𝒁 𝒑
∗
(or 𝒁 𝒏
∗
)
12 | PV181
DSA: reminder
• 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.
13 | PV181
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 used to be used,
sha-256 would be ok as well and only the first 160 bits would
be used; nowadays (2048, 256) or (3072, 256) should 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]
14 | PV181
RSA, RSA-CRT, DSA problems
• Plus: no polynomial algorithm to solve factorization or
discrete logarithm in 𝒁 𝒑
∗ and 𝒁 𝒏
∗
• Minus: there exist algorithms for factoring and
discrete log that are faster than a generic algorithm:
• A generic discrete log solver works in proportional
time to the square root of the group size, and thus
exponential in half the number of digits in the group.
• Result: bigger keys
• Solution: Elliptic Curves DSA
15 | PV181
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 is a version of DSA based on elliptic
curves.
16 | PV181
Elliptic curve example
• Example
• y2 = x3 - 3 x2 + 5 over ℚ, and ∞
• How would it look over a finite field,
• for example: Fp? for p = 7919
17 | PV181
Can you see a pattern?
Elliptic curve implementations
• Group operation over the curve: addition and doubling
18 | PV181
Elliptic curve implementations’ details
• Above operations on the finite field:
• …
19 | PV181
ECDSA: Elliptic curve 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 of elements in field / order n)
– The base point G generates a cyclic subgroup of order n in
the field.
20 | PV181
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, unless compressed
21 | PV181
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
22 | PV181
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]
23 | PV181
Post-Quantum (PQ) Schemes
• Quantum computer breaks (polynomial time) classic
public key cryptography: RSA, DSA, ECDSA
– What about symmetric cryptography?
• NIST runs a standardization for PQ schemes:
– https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4
• PQ schemes aim at higher security but are less
efficient.
• Many schemes (but not all!) are based on LWE.
• Library:
– https://libpqcrypto.org/index.html
24 | PV181
The LWE problem: search and decision
• The Learning With Errors (LWE) problem asks to recover a
secret vector s=(s1,…sn), where each si is in Zq, given a
sequence of random, “approximate” linear equations on s.
25 | PV181
https://blog.cloudflare.com/post-quantum-key-encapsulation/
Seminar Tasks
• First task – python console
• Files:
– demo.py
– RSA.py (from github)
• Good luck! ☺
26 | PV181
Task Zero
• Let’s warm up…
• I know that people called OpenSSL command line tool
from python instead of using the hazmat library.
• What is happening if you use just python and hazmat?
• Open your python and run:
from cryptography.hazmat import backends
backends.default_backend()
• How do you interpret the result?
• How many different backends there are?
• Which library is really called?
27 | PV181
First Task – documentation:
28 | PV181
Signature Schemes / Efficiency
• Do the tasks in demo.py
– Test signature schemes
– Measure the efficiency of some signature schemes
– Load OpenSSL key
• Run RSA.py and analyze the results
– What can you say about classical RSA vs RSA-CRT?
– What can you say about RSA.py vs the python library?
29 | PV181
Assignment 8 – Efficiency of Signature
Generation Algorithms
• This is a programming assignment. Please upload your
scripts/code and the required analysis via the course
webpage.
• The deadline for submission is Nov. 16, 2022, 8:00.
• Your answer should be contained in one .py file. Please
name the submission file as <uco_number>_hw8.zip. Put
there both the python code and the analysis document.
• It must contain comments so that it is reasonably easy to
understand how to run the script for evaluating each
answer.
30 | PV181
Assignment 8 - Tasks
1. Using hazmat implement the following signature schemes: RSA, DSA, ECDSA. In particular,
implement key generation, signature generation, and signature verification. [2 points]
2. Implement HMAC with SHA2 and SHA3. All implementations should be in one file. [1 point]
3. Implement all the above schemes for taking input from a file (e.g., attached alice.txt). Make sure all
your code works for large files (larger than your RAM). [2 points]
4. Perform an efficiency comparison analysis for RSA, DSA, ECDSA, HMAC-SHA2, and HMAC-SHA3.
For the signature schemes’ parameters see the following slide. Analyze key generation, signature
generation, and signature verification separately. Write a summary of your results, which primitive
seems to be the best, and for which use case. Attach such a summary to your exercise submission.
[4 points]
Remarks: (1) For the sake of computational time, use a small message to be signed. The same
message should be used for all comparisons. For the comparison also use the same hash function
(once SHA2 and once SHA3). (2) For HMAC use the key size suggested by the symmetric crypto
column in the next slide. (3) For DSA just specify the larger prime number (p). The smaller prime
number (q) will be chosen automatically. (4) By “use case”, I mean the a scheme, for example, some
algorithms are slow but have fast verification which might make them suitable for some applications.
5. Additionally, analyze whether varying the private key affects the algorithms’ execution time (or the
corresponding standard deviations of algorithms’ execution time). Please comment on the results
(what could be the reason for the observed results). [1 points]
Good luck!!!
31 | PV181
Assignment 8 – extra info
32 | PV181