Cryptography for Intel® Integrated Performance Primitives Developer Reference

Developer Reference

Contents

RSA Algorithm Functions

RSA Notation

The following description uses PKCS #1 v2.1: RSA Cryptography Standard conventions:
  • n
     - RSA modulus
  • e
     - RSA public exponent
  • d
     - RSA private exponent,
    e*d = mod lambda(n), lambda(n) = LCM
  • (n, e)
     - RSA public key
  • a pair
    (n, d)
     - so-called 1-st representation of the RSA private key
  • p, q
     - two prime factors of the RSA modulus
    n, n = p*q
  • dP
     - the
    p
    's CRT exponent,
    e*dP = 1 mod(p-1)
  • dQ
     - the
    q
    's CRT exponent,
    e*dQ = 1 mod(q-1)
  • qInv
     - the CRT coefficient,
    q*qInv = 1 mod(p)
  • a quintuple
    (p, q, dP, dQ, qInv)
     - so-called 2-nd representation of the RSA private key
All the numbers above are positive integers.
Keep in mind the following assumptions:
  • Current implementation supports RSA-1024, RSA-2048, RSA-3072 and RSA-4096 (the number denotes size of RSA modulus in bits)
  • Public exponent is fixed, e=65537
  • No specific assumption relatively "
    d
    ", except bitsize(d) ~ bitsize(n) and
    d<n
  • Size of
    p
     and
    q
     in bits is approximately the same and equals bitsize(n)/2

RSA public key operation

y = x
e
mod n, x
 and
y
 are plane- and ciphertext correspondingly

RSA private key (1-st representation) operation

x = y
d
mod n, y
 and
x
 are cipher- and plaintext correspondingly

RSA private key (2-nd representation) operation or CRT-based RSA private key operation

x1 = y
dP
mod p
x2 = y
dQ
mod q
t = (x1-x2) * qInv mod p
x = x2 + q*t

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.