View source for PKCS 1

{{short description|Technical standard}}

In [[Cryptography|cryptography]], '''PKCS #1''' is the first of a family of standards called [[PKCS|Public-Key Cryptography Standards (PKCS)]], published by RSA Laboratories. It provides the basic definitions of and recommendations for implementing the [[RSA (cryptosystem)|RSA]] algorithm for [[Public-key cryptography|public-key cryptography]].  It defines the mathematical properties of public and private keys, primitive operations for encryption and signatures, secure cryptographic schemes, and related [[Abstract Syntax Notation One|ASN.1]] syntax representations.

The current version is 2.2 (2012-10-27). Compared to 2.1 (2002-06-14), which was republished as RFC 3447, version 2.2 updates the list of allowed hashing algorithms to align them with FIPS 180-4, therefore adding SHA-224, SHA-512/224 and SHA-512/256.

==Keys==

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, {{mvar|n}}, that is the product of two distinct large [[Prime number|prime number]]s, {{mvar|p}} and {{mvar|q}}, such that <math>n = pq</math>.

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 <math>r_i</math> for some {{mvar|i}}, such that:

: <math>n = r_1 r_2 \cdots r_i,</math> for <math>i \ge 2</math>

As a notational convenience, <math>p = r_1</math> and <math>q = r_2</math>.

The RSA public key is represented as the tuple <math>(n, e)</math>, where the integer {{mvar|e}} is the public exponent.

The RSA private key may have two representations.  The first compact form is the tuple <math>(n, d)</math>, where {{mvar|d}} is the private exponent.  The second form has at least five terms {{tmath|(p, q, dp, dq, qinv)}}, 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.<ref>{{cite web| url=https://security.stackexchange.com/a/172323 |title=Can I get a public key from an RSA private key?| author=Ilmari Karonen| date=27 October 2017| work=[[Company:Stack Exchange|Stack Exchange]]}}</ref>

==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:
* RSAES-OAEP: improved '''E'''ncryption/decryption '''S'''cheme; based on the [[Optimal asymmetric encryption padding]] scheme proposed by  Mihir Bellare and Phillip Rogaway.
* RSAES-PKCS1-v1_5: older encryption/decryption scheme as first standardized in version 1.5 of PKCS #1.

Note: A small change was made to RSAES-OAEP in PKCS #1 version 2.1, causing RSAES-OAEP in PKCS #1 version 2.0 to be totally incompatible with RSA-OAEP in PKCS #1 version 2.1 and version 2.2.

There are also two schemes for dealing with signatures:
* RSASSA-PSS: improved '''P'''robabilistic '''S'''ignature '''S'''cheme with appendix; based on the [[Probabilistic signature scheme|probabilistic signature scheme]] originally invented by Bellare and Rogaway.
* RSASSA-PKCS1-v1_5: old '''S'''ignature '''S'''cheme with '''A'''ppendix as first standardized in version 1.5 of PKCS #1.

The two signature schemes make use of separately defined encoding methods:
* EMSA-PSS: encoding method for signature appendix, probabilistic signature scheme.
* EMSA-PKCS1-v1_5: encoding method for signature appendix as first standardized in version 1.5 of PKCS #1.

The signature schemes are actually signatures ''with appendix'', which means that rather than signing some input data
directly, a [[Hash function|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 {{IETF RFC|2313}}.
* Version 2.0, September 1998. Republished as {{IETF RFC|2437}}. Introduced the RSAEP-OAEP encryption scheme.
* Version 2.1, June 2002. Republished as {{IETF RFC|3447}}. Introduced multi-prime RSA and the RSASSA-PSS signature scheme
* Version 2.2, October 2012. Republished as {{IETF RFC|8017}}.

== Implementations ==
Below is a list of cryptography libraries that provide support for PKCS#1:

*[[Software:Botan (programming library)|Botan]]
*[[Software:Bouncy Castle (cryptography)|Bouncy Castle]]
*[[Software:BSAFE|BSAFE]]
*[[Software:Cryptlib|cryptlib]]
*[[Software:Crypto++|Crypto++]]
*[[Software:Libgcrypt|Libgcrypt]]
*[[Software:Mbed TLS|mbed TLS]]
*[[Software:Nettle (cryptographic library)|Nettle]]
*[[Software:OpenSSL|OpenSSL]]
*wolfCrypt

== Attacks ==
Multiple attacks were discovered against PKCS #1 v1.5.<ref name="Coron">{{cite book|author=Jean-Sébastien Coron, Marc Joye, David Naccache, and Pascal Paillier|title=Advances in Cryptology — EUROCRYPT 2000 |volume=1807|publisher=EUROCRYPT|year=2000|pages=369–381|url=https://www.iacr.org/archive/eurocrypt2000/1807/18070374-new.pdf|doi=10.1007/3-540-45539-6|isbn=978-3-540-67517-4|series=Lecture Notes in Computer Science|s2cid=8447520}}</ref><ref name="Bard12"/>

In 1998, Daniel Bleichenbacher published a seminal paper on what became known as [[Adaptive chosen-ciphertext attack#Practical attacks|Bleichenbacher's attack]] (also known as "million message attack").<ref name="Bard12">{{cite thesis
| url=https://hal.inria.fr/hal-00691958v3
| title=Efficient Padding Oracle Attacks on Cryptographic Hardware
|author=Romain Bardou |author2=Riccardo Focardi |author3=Yusuke Kawamoto |author4=Lorenzo Simionato |author5=Graham Steel |author6=Joe-Kai Tsay
| journal=Rr-7944
| publisher=INRIA
| date=2012
| page=19| type=report
}}</ref><ref>{{IETF RFC|3218}} – Preventing the Million Message Attack on Cryptographic Message Syntax</ref> 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.<ref name="Coron"/>
With slight variations this vulnerability still exists in many modern servers.<ref>{{Cite web |url = https://robotattack.org |title = ROBOT attack: Return Of Bleichenbacher's Oracle Threat |author=Hanno Böck |author2=Juraj Somorovsky |author3=Craig Young |access-date = February 27, 2018 }}</ref>

In 2006, Bleichenbacher presented a new forgery attack against the signature scheme RSASSA-PKCS1-v1_5.<ref>{{cite book
| chapter=Analysis on Bleichenbacher's Forgery Attack
|author=Tetsuya Izu |author2=Masahiko Takenaka |author3=Takeshi Shimoyama
| title=The Second International Conference on Availability, Reliability and Security (ARES'07)
| pages=1167–1174
| publisher=IEEE
| date=April 2007
| doi=10.1109/ARES.2007.38| isbn=978-0-7695-2775-8
| s2cid=2459509
}}</ref>

==See also==
*[[Comparison of cryptography libraries]]

==References==
{{Reflist}}

==External links==
* {{IETF RFC|8017}} - PKCS #1: RSA Cryptography Specifications Version 2.2
* {{Webarchive|url=https://web.archive.org/web/20160410165357/http://www.emc.com/collateral/white-papers/h11300-pkcs-1v2-2-rsa-cryptography-standard-wp.pdf|date=April 10, 2016|title=PKCS #1 v2.2: RSA Cryptography Standard}}
* {{Webarchive|url=https://web.archive.org/web/20040404183951/http://www.rsasecurity.com/rsalabs/technotes/rsa-pss.html|date=2004-04-04|title=Raising the Standard for RSA Signatures: RSA-PSS}}

{{Cryptography navbox}}

[[Category:Cryptography standards]]
[[Category:Digital signature schemes]]
[[Category:Digital Signature Standard]]

{{Sourceattribution|PKCS 1}}