Length of
cryptographic keys
Zdeněk Říha
Security of RSA
 We choose randomly 2 primes and compute n and φ(n) :
 p, q
 n = p·q
 φ(n) = (p-1)(q-1).
 e is chosen such that gcd(e, φ(n)) = 1.
 We compute d = e-1 (mod φ(n)).
 Public key: n, e.
Private parameters: p, q, d.
Private key: d.
 Security of RSA cryptosystem is based on the problem
of factoring large numbers
 If public n can be factored into p and q, we can calculate
φ(n) and derive d from e.
 Integer factorization is taught at primary schools
 But when integers are very big it takes very long time
even for fast computers to factor the number
Computational Security
 Unconditional vs. computational security
 Security based on a hard problem
 The problem is solvable, but it takes
impractically long time to solve
 The attacker cannot wait thousands/millions
of years to break the encryption
 Our expectations can change:
 Progress in the speed of HW
 Progress in the efficiency of algorithms
History of RSA Security
 RSA is considered secure
 But the key size does matter
 1977: published in “Scientific American”
 RSA-129 (129 decimal digits of modulus n)
 Challenge of 100 dollars
 40 quadrillion years estimated to factor …
 Factored in 1994
 “The magic words are squeamish ossifrage.”
History of RSA Security II
 1999
 512 bit integer was factorized
 2005
 663 bit integer was factorized
 January 2010
 768 bit integer was factorized
 1024 bit integers are (probably) not factorable
at the moment
Security of RSA
Source: P. Layland, RSA Security and Integer Factorization: The Thirty Years
War from 1990 to 2020, IS2 2010, Praha
Key size
 Algorithms are public & keys must be secret
 Key must be large enough that a brute force
attack is infeasible
 Depending on the algorithm used it is
common to have different key sizes for the
same level of security
 Representing the level of security – number of
combinations needed for the brute force attack
 E.g. 1024 bit RSA key equivalent to 80 bit
symmetric encryption key
Comparable strengths of
cryptosystems
Source:
NIST SP800-57
Security strengths of hash
functions
Source:
NIST SP800-57
Security strengths of hash
functions
Source:
NIST SP800-57
Recommended key sizes
Source:
NIST SP800-57
“Acceptable” indicates that the algorithm or key length is not known to be insecure.
“Deprecated” means that the use of an algorithm or key length that provides the
indicated security strength may be used if risk is accepted
“Legacy use” means that an algorithm or key length may be used because of its use in
legacy applications
“Disallowed” means that an algorithm or key length shall not be used
for applying cryptographic protection.
Crypto period
Source:
NIST SP800-57
Crypto period example
Source:
NIST SP800-57
Recommended crypto periods
Source:NIST SP800-57
ETSI recommendation (RSA)
 Source: ETSI TS 102 176-1 V2.1.1 (2011-07)
 Recommended key sizes for RSA and
rsagen1 for a resistance during X years
 Starting date: 2011
ETSI recommendation (RSA)
 Source: ETSI TS 102 176-1 V2.1.1 (2011-07)
 Recommended padding schemes for RSA
and rsagen1
 Starting date: 2011
ETSI recommendation (DSA)
 Source: ETSI TS 102 176-1 V2.1.1 (2011-07)
 Recommended key sizes for DSA
 Starting date: 2011
ETSI recommendation
(ECDSA)
 Source: ETSI TS 102 176-1 V2.1.1 (2011-07)
 Recommended key sizes for ECDSA
 Starting date: 2011
ETSI recommendation (hash
functions)
 Source: ETSI TS 102 176-1 V2.1.1 (2011-07)
 Recommended hash functions
 Starting date: 2011
ETSI recommendation
 Source: ETSI TS 102 176-1 V2.1.1 (2011-07)
 Recommended signature schemes
 Starting date: 2011
Česká republika & EU & ETSI
 EU
 SMĚRNICE 1999/93/EC EVROPSKÉHO PARLAMENTU A
RADY ze dne 13. prosince 1999 o zásadách Společenství
pro elektronické podpisy
 ČR
 Zákon č. 227/2000 Sb. o elektronickém podpisu
 Několikrát novelizován
 Podzákonné předpisy
 Nařízení vlády č. 495/2004 Sb, kterým se provádí zákon č.
227/2000 Sb., o elektronickém podpisu a o změně
některých dalších zákonů
 Vyhláška č. 496/2004 Sb. k elektronickým podatelnám
 Vyhláška č. 378/2006 Sb., o postupech kvalifikovaných
poskytovatelů certifikačních služeb
Česká republika & EU & ETSI
 Vyhláška č. 378/2006 Sb.
 „používá důvěryhodné systémy a postupy, které splňují
požadavky standardu pro tyto systémy, který je uveden v
bodu 1 přílohy č. 1 této vyhlášky“
 1. CWA 14167-1 – Security Requirements for Trustworthy
Systems Managing Certificates for Electronic Signatures –
Part 1: System Security Requirements.
 „Security requirements for TWSs also include a minimum
set of requirements to be fulfilled by the signature
algorithms and their parameters allowed for use by CSPs.
These requirements are provided in [ALGO].“
 [ALGO] ETSI SR 002 176 - Electronic Signatures and
Infrastructures (ESI); Algorithms and Parameters for
Secure Electronic Signatures.
Stanovisko MV ČR
 „V návaznosti na směrnici ES č. 1999/93/EC o zásadách Společenství pro
elektronické podpisy a v ní obsažený princip vzájemného uznávání
kvalifikovaných certifikátů vydaných v kterémkoliv členském státu EU je
nezbytné vycházet z dokumentu ALGO paper, který stanoví, že od 1. 1. 2010 je
algoritmus SHA-1 „unusable“ a je tedy nezbytné ukončit jeho používání pro
oblast elektronického podpisu a zahájit přechod na bezpečnější algoritmy třídy
SHA-2. Česká republika patří k těm členským státům, ve kterých je tento
přechod rozložen do delšího časového období. Je však nezbytné jej realizovat,
a tak zachovat důvěru uživatelů v bezpečnost elektronického podpisu.“
 poskytovatelé certifikačních služeb přestanou vydávat kvalifikované
certifikáty s algoritmem SHA-1 nejpozději do 31. 12. 2009,
 poskytovatelé certifikačních služeb zahájí vydávání kvalifikovaných
certifikátů s hashovací funkcí třídy SHA-2 nejpozději 1. 1. 2010 (mohou tak
však učinit kdykoliv dříve); tato změna se samozřejmě týká i vydávání
kořenových certifikátů, kterými poskytovatel certifikačních služeb označuje
jím vydané certifikáty,
 aplikace, ve kterých je elektronický podpis používán, musí podporovat
nejpozději od 1. 1. 2010 všechny algoritmy třídy SHA-2,
 podpora algoritmu SHA-1 musí být v aplikacích zachována minimálně do
31.12.2010
Zdroj: MV ČR
Dohoda českých
akreditovaných CA
 „Kvalifikované certifikáty s hashovací funkcí třídy SHA-2, které
začnou vydávat nejpozději od 1. ledna 2010, budou všichni tři
poskytovatelé přednostně nabízet s hashovací funkcí SHA-256 v
kombinaci s algoritmem RSA s délkou klíče 2048 bitů.
Poskytovatel certifikačních služeb může na základě vlastního
rozhodnutí a základě požadavků svých zákazníků vydávat
kvalifikované certifikáty i s některou z dalších funkcí z rodiny
SHA-2, tj. SHA-224, SHA-384 nebo SHA-512.“
 Ministerstvo vnitra nemá námitek proti této dohodě. Tvůrce
aplikací pracujících se zaručeným elektronickým podpisem
založeném na kvalifikovaném certifikátu je však nutné upozornit,
že je nezbytné vytvořit prostředí pro akceptování všech čtyř
hashovacích funkcí rodiny SHA-2, a to i s ohledem na akceptaci
kvalifikovaných certifikátů vydaných v jiných členských státech
EU
Zdroj: MV ČR
Akreditované CA
 První certifikační autorita, a. s.
 Česká pošta, s. p.,
 eIdentity a. s.,
Zdroj: MV ČR
Poslední změny zákona
 „Za elektronický podpis splňující požadavky
odstavce 1 se považuje rovněž zaručený
elektronický podpis založený na kvalifikovaném
certifikátu vydaném poskytovatelem certifikačních
služeb usazeném v některém z členských států
Evropské unie, byl-li kvalifikovaný certifikát vydán v
rámci služby vedené v seznamu důvěryhodných
certifikačních služeb, jako služba, pro jejíž
poskytování je poskytovatel certifikačních služeb
akreditován, nebo jako služba, nad jejímž
poskytováním je vykonáván dohled.“
Zdroj:
§ 11 zákona 227/2000 Sb.
Jak na to v praxi
 Každá země EU vydává seznam
důvěryhodných certifikačních služeb
 TSL: Trusted Services List
 Ne každá země však takový seznam digitálně
podepisuje …
 Seznam je k dispozici mimo jiné na
http://tsl.gov.cz/
 Řada odkazů na lidsky čitelné a strojově
zpracovatelně (XML) TSL seznamy zemí EU
Seznam TSL
Služba MV ČR: CertIQ
 Určí, zda certifikát byl vydán jako
kvalifikovaný v nějaké zemi EU
ICAO recommendation
 International Civil Aviation Organization
 Electronic passports
 Data signed by the issuing country to protect
integrity
 One CA per country, certificates issued for entities
producing passports (so called Document
Signers).
 Standard validity of passports: 10 years
ICAO recommendations
 RSA (UK, CZ, France, …)
 Padding: PKCS#1 v1.5, PSS (recommended)
 For CA: min 3072 bits
 For DS: min 2048 bits
 DSA
 For CA: min 3072/256 bits
 For DS: min 2048/224 bits
 ECDSA (Germany, Switzerland, …)
 For CA: min 256 bits
 For DS: min 224 bits
 Hash functions
 SHA-1, SHA-2
Source: ICAO Doc. 9303
ICAO recommendations
 “It is therefore RECOMMENDED that the
maximum period the Document Signer Key is
used to sign passport documents be three
months. For States that generate large
numbers of MRTDs, several current
document signing keys MAY be issued at any
given time.”
Source: ICAO Doc. 9303