PV181 Laboratory of security
and applied cryptography
Part 3, seminar 10:
Advanced Topics
Łukasz Chmielewski
chmiel@fi.muni.cz
| PV1811
Outline
• Organizational
• Finishing Seminar’s 3 exercises (10min)
– Discuss the most common issue in the solutions
– Optional task discussion
• Recall from the last seminars
– We concentrate on signatures
• RSA, RSA-CRT
• DSA, ECDSA
• Efficiency
• Post Quantum
2 | PV181
Organization
• 22.11 Advanced Crypto by Lukasz +HW
• 29.11: Biometrics by Agata & Katarina +HW
• 6.12: Crypto-libraries protected against hardware
attacks by Lukasz +HW
• 13.12: Passwords Security by Alessia and Lukasz
+HW
3 | PV181
Issues in Solutions
• Multiple OS, libraries, OpenSSL versions
– In some cases even if you tell me the details, I cannot run
it easily. Let’s double-check the code together.
• Encryption of large files:
– Encrypting line by line; line length might be very long
– Encrypting chunks of files separately
• they can be re-reordered
– Forgetting to run finalize after encryption.
4 | PV181
Finishing Seminar 3 last tasks
• demo.py
• Tasks 6 and 7…
– Did anyone try to do it?
5 | 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: …
6 | 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
7 | 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
| PV1818
Recall: Asymmetric cryptosystem
Digital signature scheme
9 | 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?
10 | PV181
RSA: reminder
1. Secret primes 𝑝, 𝑞: 𝑛 = 𝑝 ∙ 𝑞
2. Public exponent 𝑒:
gcd 𝑒, (𝑝 − 1) = gcd 𝑒, (𝑞 − 1) = 1
3. Private exponent 𝑑: 𝑑 ∙ 𝑒 ≡ 1 𝑚𝑜𝑑 𝜑 𝑛
Encryption (public 𝑛, 𝑒): 𝐸 𝑚 = 𝑚 𝑒 𝑚𝑜𝑑 𝑛 = 𝑐
Decryption (private 𝑛, 𝑑): 𝐷 𝑐 = 𝑐 𝑑 𝑚𝑜𝑑 𝑛 = 𝑚
11 | 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))
13 | PV181
Discrete Logarithm Problem 𝒁 𝒑
∗
(or 𝒁 𝒏
∗
)
14 | 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.
15 | 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]
16 | 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
17 | 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.
18 | 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
19 | PV181
Can you see a pattern?
Elliptic curve implementations
• Group operation over the curve: addition and doubling
20 | PV181
Elliptic curve implementations’ details
• Above operations on the finite field:
• …
21 | 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.
22 | 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
23 | 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
24 | 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]
25 | 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
26 | 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.
27 | PV181
https://blog.cloudflare.com/post-quantum-key-encapsulation/
Seminar Tasks
• A short demo based on MQDSS
– https://mqdss.org/
• I used the following library:
– https://libpqcrypto.org/python.html
• Signature scheme based on multivariate quadratic
problem
28 | PV181
Seminar Tasks
• First task – python console
• Files:
– demo.py
– RSA.py (from github)
• Good luck! ☺
29 | 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?
30 | PV181
First Task – documentation:
31 | 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?
32 | PV181
Assignment 7 – 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. 29, 2023, 8:00.
– -3 points for each started 24h after the deadline.
• Your code should be contained in one .py file. Please name the
submission file as <uco_number>_hw7.zip. Put there both the
python code, the analysis document, and all data produced
during analysis (as long as the size is reasonable).
• The code must contain comments so that it is reasonably easy
to understand how to run the script for evaluating each answer.
33 | PV181
Assignment 7 - 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.
To have reliable results, perform operations a number of times and average results. [4 points]
Remarks: (1) For the sake of computational time, use a small message (e.g., a text file) 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 a scheme, for example, some algorithms are slow but have fast verification, which might make them
suitable for some applications. 5) Include file reading in signature generation time.
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 point]
6. Bonus: perform a similar analysis to point 4 for a larger file (approximately 100Mb) What is the
difference here? What could be the reason of the change (if any)? [1 point]
Good luck!!!
34 | PV181
Assignment 7 – extra info
35 | PV181