Overview | Package | Class | Use | Tree | Deprecated | Index | Help
| Cryptix V3.2
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## cryptix.provider.rsa
Class RSAAlgorithm

    java.lang.Object
      |
      +--cryptix.provider.rsa.RSAAlgorithm

public final class RSAAlgorithm
extends java.lang.Object

A class that calculates the RSA algorithm. A single method is used for encryption, decryption, signing and verification:

- for encryption and verification, the public exponent, e, should be given.
- for decryption and signing, the private exponent, d, should be given.

The purpose of having this as a separate class is to avoid duplication between the RSA Cipher and Signature implementations.

References:

1. Donald E. Knuth, The Art of Computer Programming, ISBN 0-201-03822-6 (v.2) pages 270-274.

2. ANS X9.31, Appendix B.

Copyright © 1997 Systemics Ltd on behalf of the Cryptix Development Team.
All rights reserved.

$Revision: 1.7 $

Since:
  Cryptix 2.2.2
Author:
  Raif S. Naffah, David Hopwood

Method Summary
`static java.math.BigInteger` | `rsa(java.math.BigInteger X, java.math.BigInteger n, java.math.BigInteger exp)` Computes the RSA algorithm, without using the Chinese Remainder Theorem.
`static java.math.BigInteger` | `rsa(java.math.BigInteger X, java.math.BigInteger n, java.math.BigInteger exp, java.math.BigInteger p, java.math.BigInteger q, java.math.BigInteger u)` Computes the RSA algorithm.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Method Detail

### rsa

    public static java.math.BigInteger rsa(java.math.BigInteger X,
                                           java.math.BigInteger n,
                                           java.math.BigInteger exp,
                                           java.math.BigInteger p,
                                           java.math.BigInteger q,
                                           java.math.BigInteger u)

  Computes the RSA algorithm. If p is null, straightforward modular exponentiation is used.

  Otherwise, this method uses the Chinese Remainder Theorem (CRT) to compute the result given the known factorisation of the public modulus n into two relatively prime factors p and q. The arithmetic behind this method is detailed in [1] and [2].

  The comments that follow, which are edited from the PGP `mpilib.c` file with p and q reversed, make the practical algorithmic implementation clearer:

  > Y = X**d (mod n) = X**d (mod pq)

  We form this by evaluating:

  > p2 = plain**d (mod p) and
  > q2 = plain**d (mod q)

  and then combining the two by the CRT.

  Two optimisations of this are possible. First, we reduce X modulo p and q before starting, since:

  > x**a (mod b) = (x (mod b))**a (mod b)

  Second, since we know the factorisation of p and q (trivially derived from the factorisation of n = pq), and input is relatively prime to both p and q, we can use Euler's theorem:

  > X**phi(m) = 1 (mod m),

  to throw away multiples of phi(p) or phi(q) in d. Letting

  > ep = d (mod phi(p)) and
  > eq = d (mod phi(q))

  then combining these two speedups, we only need to evaluate:

  > p2 = (X mod p)**ep (mod p) and
  > q2 = (X mod q)**eq (mod q).

  Now we need to apply the CRT. Starting with:

  > Y = p2 (mod p) and
  > Y = q2 (mod q)

  we can say that:

  > Y = q2 + kq

  and if we assume that:

  > 0 <= q2 < q, then
  > 0 <= Y < pq for some 0 <= k < p

  Since we want:

  > Y = p2 (mod p),

  then

  > kq = (p2 - q2) (mod q)

  > > Since p and q are relatively prime, q has a multiplicative inverse u mod p. In other words, uq = 1 (mod p).

  > > Multiplying by u on both sides gives:

  > > > k = u * (p2 - q2) (mod p)

  > > Once we have k, evaluating kq + q2 is trivial, and that gives us the result.

  Parameters:
    `X` - the BigInteger to be used as input.
    `n` - the public modulus.
    `exp` - the exponent (e for encryption and verification, d for decryption and signing).
    `p` - the first factor of the public modulus.
    `q` - the second factor of the public modulus.
    `u` - the multiplicative inverse of q modulo p.
  Returns:
    the result of the computation.

### rsa

    public static java.math.BigInteger rsa(java.math.BigInteger X,
                                           java.math.BigInteger n,
                                           java.math.BigInteger exp)

  Computes the RSA algorithm, without using the Chinese Remainder Theorem.
  Parameters:
    `X` - the BigInteger to be used as input.
    `n` - the public modulus.
    `exp` - the exponent (e for encryption and verification, d for decryption and signing).
  Returns:
    the result of the computation.

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
| Cryptix V3.2
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright (C) 1995-2000 The Cryptix Foundation Ltd. All rights reserved.