In June 2018 the SOG-IS Crypto Working Group released "SOGIS Agreed Cryptographic Mechanisms" version 1.1, a new recommendation about the acceptable cryptographic algorithms under the SOG-IS Crypto Evaluation Scheme. (The SOG-IS Crypto Evaluation Scheme is a set of requirements and evaluation procedures related to cryptographic aspects of Common Criteria based security evaluations of IT products.) The released document is also considered relevant by the European Telecommunications Standards Institute (ETSI) for choosing the cryptographic algorithms used in trust services, because the so-called “Algo Paper”, the technical specification TS 119 312 builds on it as well.

The trust services and the evidences they generate (for example electronic signatures, electronic seals, timestamps etc.) defined by the eIDAS regulation are based on the Public Key Infrastructure (PKI) technology, the core elements of which are cryptographic algorithms with asymmetric keys. (Such algorithms are essential for the creation of electronic signatures, electronic seals and related certificates and timestamps as well.) The basic idea behind asymmetric key encryption is that every participant has two different, but strictly corresponding, keys: any data enciphered with one of the keys can only be deciphered with the other key and vice versa. One of the keys must be kept secret (this is called the private key), while the other key should be published (this is called the public key). The encryption is secure if one cannot calculate or deduce the private key from the public key.

Nowadays, one the most relevant asymmetric key encryption methods is the RSA algorithm, named after the initials of its inventors (Rivest, Shamir, Adleman). The algorithm’s encryption and decryption methods are based on modular exponentiation and integer division, and the PKI keys are the parameters of these operations. The public key includes the modulus used in the integer division operation, which is a product of two large (a couple hundred digit long) prime numbers. If the two prime numbers were known, the private key would be calculable. The security of the RSA algorithm is derived from the fact that the two prime factors of this large product are difficult to find. No efficient procedure is known to solve this problem. This task in number theory (finding the factors of a large composite number) is called prime factorization problem, which mathematicians have been studying since ancient times. Thus, the foundation of the RSA algorithm is old and well-known number theory, which makes it – although admittedly not impossible – rather highly unlikely that someone is suddenly able to "break" it (i.e. calculate the private key from a public key). However, the disadvantage of the RSA algorithm is that very large keys (such as 2048, 3072 or 4096 bits long) must be used to make the factorization problem a sufficiently difficult task. In addition, due to technological advances and the constant increase in computing capacity, longer and longer keys have to be selected to maintain the level of security.

Cryptographic keys (especially private keys) are very sensitive and valuable data that must be kept secret, so special hardware devices, such as smart cards are often used to store and manage them. In case of smart cards, it may be a problem when they do not have enough memory to store very large keys, or they perform cryptographic operations too slowly with very large keys.

There is a solution to this problem, check out our next post about elliptic curves!

References / Further information:

- https://www.sogis.eu/documents/cc/crypto/SOGIS-Agreed-Cryptographic-Mechanisms-1.1.pdf
- https://www.etsi.org/deliver/etsi_ts/119300_119399/119312/01.02.02_60/ts_119312v010202p.pdf

Author: Kornél RÉTI

© 2019 Microsec ltd. | Company registration number: 01-10-047218 | Tax number: 23584497-2-41

Scroll to Top