PKCS 1

The PKCS #1 standard defines the mathematical definitions and properties that RSA public and private keys must have. The traditional key pair is based on a modulus, , that is the product of two distinct large prime numbers, and , such that n = pq. Starting with version 2.1, this definition was generalized to allow for multi-prime keys, where the number of distinct primes may be two or more. When dealing with multi-prime keys, the prime factors are all generally labeled as r_i for some , such that: : n = r_1 r_2 \cdots r_i, for i \ge 2 As a notational convenience, p = r_1 and q = r_2. The RSA public key is represented as the tuple (n, e), where the integer is the public exponent. The RSA private key may have two representations. The first compact form is the tuple (n, d), where is the private exponent. The second form has at least five terms , or more for multi-prime keys. Although mathematically redundant to the compact form, the additional terms allow for certain computational optimizations when using the key. In particular, the second format allows to derive the public key. == Primitives ==

The standard defines several basic primitives. The primitive operations provide the fundamental instructions for turning the raw mathematical formulas into computable algorithms. • I2OSP – Integer to Octet String Primitive – Converts a (potentially very large) non-negative integer into a sequence of bytes (octet string). • OS2IP – Octet String to Integer Primitive – Interprets a sequence of bytes as a non-negative integer • RSAEP – RSA Encryption Primitive – Encrypts a message using a public key • RSADP – RSA Decryption Primitive – Decrypts ciphertext using a private key • RSASP1 – RSA Signature Primitive 1 – Creates a signature over a message using a private key • RSAVP1 – RSA Verification Primitive 1 – Verifies a signature is for a message using a public key == Schemes ==

By themselves the primitive operations do not necessarily provide any security. The concept of a cryptographic scheme is to define higher level algorithms or uses of the primitives so they achieve certain security goals. There are two schemes for encryption and decryption: • : older Encryption/decryption Scheme (ES) as first standardized in version 1.5 of PKCS #1. Known-vulnerable. • : improved ES; based on the optimal asymmetric encryption padding (OAEP) scheme proposed by Mihir Bellare and Phillip Rogaway. Recommended for new applications. There are also two schemes for dealing with signatures: • : old Signature Scheme with Appendix (SSA) as first standardized in version 1.5 of PKCS #1. Unforgeable, according to Jager et al. (2018). • : improved SSA; based on the probabilistic signature scheme (PSS) originally invented by Bellare and Rogaway. Recommended for new applications. The two signature schemes make use of separately defined encoding methods: • : old encoding method for signature appendix (EMSA) as first standardized in version 1.5 of PKCS #1. • : improved EMSA, based on the probabilistic signature scheme. Recommended for new applications. The signature schemes are actually signatures with appendix, which means that rather than signing some input data directly, a hash function is used first to produce an intermediary representation of the data, and then the result of the hash is signed. This technique is almost always used with RSA because the amount of data that can be directly signed is proportional to the size of the keys; which is almost always much smaller than the amount of data an application may wish to sign. == Version history ==

• Versions 1.1–1.3, February through March 1991, privately distributed. • Version 1.4, June 1991, published for NIST/OSI Implementors' Workshop. • Version 1.5, November 1993. First public publication. Republished as . • Version 2.0, September 1998. Republished as . Introduced the RSAEP-OAEP encryption scheme. • Version 2.1, June 2002. Republished as . Introduced multi-prime RSA and the RSASSA-PSS signature scheme • Version 2.2, October 2012. Republished as . == Implementations ==

Below is a list of cryptography libraries that provide support for PKCS#1: • Botan • Bouncy Castle • BSAFE • cryptlib • Crypto++ • Libgcrypt • mbed TLS • Nettle • OpenSSL • wolfCrypt == Attacks ==

Multiple attacks were discovered against PKCS #1 v1.5, specifically its padding scheme. PKCS #1 was subsequently updated in the release 2.0 and patches were issued to users wishing to continue using the old version of the standard. • Böck et al. (2018) report that many modern HTTPS servers are vulnerable to a variation of the attack. TLS 1.2 contains anti-Bleichenbacher countermeasures, but the workarounds are not correctly implemented in many software due to their sheer complexity. In 2006, Bleichenbacher presented a new forgery attack against the signature scheme RSASSA-PKCS1-v1_5. Variants of this attack are reported in 2008 and 2014. This class of attack exploits a flawed implementation of the signature verification; a proper implementation would not be vulnerable. == See also ==