pkcs1

PKCS #1 : RSA Cryptography Standard: 

PKCS #1 : RSA Cryptography Standard Jessica Staddon RSA Laboratories PKCS Workshop October 7, 1998

Outline: 

Outline Update on status of v2.0 Overview of v2.0 content Technical highlights of v2.0 Possibilities for 2.x !

Status of v2.0: 

Status of v2.0 v2.0 was posted for 30-day review on 7/14/98 v2.0 was submitted as an Internet-Draft to the IETF on 8/6/98 a few comments were received…and the final document was posted on 9/4

Overview of v2.0: 

Overview of v2.0 Encryption schemes: OAEP-based encryption (Bellare-Rogaway) v1.5 encryption, for backward compatibility v1.5 signature scheme with appendix ASN.1 syntax new OIDs for the OAEP-based scheme

Technical Highlights: 

Technical Highlights Style RSAES-OAEP Auxiliary functions ASN.1

Style and terminology of v2.0 is similar to IEEE P1363:: 

Style and terminology of v2.0 is similar to IEEE P1363: Primitives encryption and decryption signature and verification data conversion Encryption and signature schemes Encoding methods for encryption and signatures w/ appendix Auxiliary functions

Primitives: 

Primitives Basic mathematical operations Primitives are used in schemes e.g. RSAEP( (n, e), m): 1. If m is not between 0 and n-1, output 'message representative out of range' and stop. 2. Let c = me mod n. 3. Output c.

Schemes: 

Schemes Combine primitives and other techniques (e.g. encoding methods) to achieve a particular security goal.

RSAES-OAEP (Section 7.1): 

RSAES-OAEP (Section 7.1) Within the random oracle model: Provably secure can tie security to the RSA function Plaintext-aware 'can’t' generate valid ciphertext w/o the plaintext chosen-ciphertext attacks are ineffective

RSAES-OAEP: 

RSAES-OAEP Encrypt (public key, M, P): EM = EME-OAEP-Encode (M, P) C = RSAEP (public key, EM) Decrypt (private key, C, P): EM = RSADP (private key, C) M = EME-OAEP-Decode (EM, P) M, C bounded, P arbitrary length

EME-OAEP-Encode(M, P, emLen) (Section 9.1.1.1): 

EME-OAEP-Encode(M, P, emLen) (Section 9.1.1.1) Options: Hash output length hLen MGF mask generation function Input: M length at most emLen-1-2hLen P encoding parameters emLen length of output Output: encoded message, EM (length emLen) or, 'message too long', or 'parameter string too long' RSAES-OAEP-Encrypt calls this with emLen = k -1

EME-OAEP-Encode: 

EME-OAEP-Encode

Auxiliary Functions (Section 10): 

Auxiliary Functions (Section 10) Hash functions deterministic functions, variable length input, fixed length output collision resistance important to deter forgery of v1.5 signatures SHA-1 is recommended for EME-OAEP MD2, MD5 and SHA-1 are recommended for all other encoding methods

Slide14: 

Mask generation functions deterministic functions take variable length input and output string of any predetermined length v2.0 defines an MGF based on a hash function, MGF1 SHA-1 is the recommended hash function for MGF1

MGF1(Z, l): 

MGF1(Z, l) Z is a seed, l is the length of the mask (the output) Let T be the empty string For counter from 0 to  l / hLen -1, do the following: a. Convert counter to an octet string C of length 4 with the primitive I2OSP: C = I2OSP (counter, 4) b.Concatenate the hash of the seed Z and C to the octet string T: T = T || Hash (Z || C) Output the leading l octets of T as the octet string mask.

ASN.1 for RSA-OAEP (Section 11.2.1): 

ASN.1 for RSA-OAEP (Section 11.2.1) The syntax allows for increased functionality-- other hash functions, other types of MGFs, etc. OID for the RSAES-OAEP encryption scheme: id-RSAES-OAEP OBJECT IDENTIFIER ::= {pkcs-1 7} The parameters field associated with this OID in an AlgorithmIdentifier shall have type RSAEP-OAEP-params:

Slide17: 

RSAES-OAEP-params ::= SEQUENCE { hashFunc [0] AlgorithmIdentifier{{oaepDigestAlgorithms}} DEFAULT sha1Identifier, maskGenFunc [1] AlgorithmIdentifier{{pkcs1MGFAlgorithms}} DEFAULT mgf1SHA1Identifier, pSourceFunc [2] AlgorithmIdentifier {{pkcs1pSourceAlgorithms}} DEFAULT pSpecifiedEmptyIdentifier }

Slide18: 

In v2.0, P is an octet string that’s specified explicitly, although the syntax is more flexible: pkcs1pSourceAlgorithms ALGORITHM-IDENTIFIER ::= {{OCTET STRING IDENTIFIED BY id-pSpecified}} (encoding parameters are specified explicitly) id-pSpecified OBJECT IDENTIFIER ::= {pkcs-1 9} The parameters field for id-pSpecified shall have type OCTET STRING, containing the encoding parameters. pSpecifiedEmptyIdentifier ::=AlgorithmIdentifier {id-pSpecified, OCTET STRING SIZE (0) }

If defaults for all the fields in RSAES-OAEP-params are used then the AlgID has the value:: 

If defaults for all the fields in RSAES-OAEP-params are used then the AlgID has the value: RSAES-OAEP-Default-Identifier ::= AlgorithmIdentifier { id-RSAES-OAEP, {sha1Identifier, mgf1SHA1Identifier, pSpecifiedEmptyIdentifier } }

Possibilities for v2.x: 

Possibilities for v2.x Signature schemes provable security (PSS) message recovery (PSS-R, ISO/IEC 9796) other options (X9.31…) Key generation methods Key validation methods

ISO/IEC 9796: 

ISO/IEC 9796 An international standard for signatures with message recovery Process involves padding, extending and adding redundancy to messages Not provably secure

X9.31 rDSA: 

X9.31 rDSA A hash based encoding method: M  EM = header || padding || H(M) || trailer  f-1(EM) (f-1 denotes the signature operation)

Key generation methods: 

Key generation methods Prime generation methods from ANSI draft X9.79: Prime Number Generation and Validation Methods? Sieving procedures? Primality tests (probabilistic/deterministic)?

Key validation methods : 

Key validation methods Still an area of research… Some possibilities... methods for showing n is product of two primes method of Liskov and Silverman for showing that the two factors of n are nearly equal