IMPLEMENTATION MODULE RSA;

        (********************************************************)
        (*                                                      *)
        (*           The RSA public key cryptosystem            *)
        (*                                                      *)
        (*  Programmer:         P. Moylan                       *)
        (*  Last edited:        21 January 2021                 *)
        (*  Status:             Working                         *)
        (*                                                      *)
        (*      In case you're wondering what RSA stands for,   *)
        (*      it's Rivest-Shamir-Adleman, after the           *)
        (*      inventors of the algorithm.                     *)
        (*                                                      *)
        (********************************************************)


FROM SYSTEM IMPORT CAST, CARD32;

FROM RSAKeys IMPORT RSAKeyType;

IMPORT BigNum;

FROM BigNum IMPORT
    (* type *)  BN;

(************************************************************************)
(*                     RSA ENCRYPTION AND DECRYPTION                    *)
(************************************************************************)

PROCEDURE PubKeyEncode (m: BN;  key: RSAKeyType): BN;

    (* m is a numerical encoding of the message, with 0 <= M < key.n    *)
    (* We produce a ciphertext using only the public part of the key.   *)

    (* Remark: we cannot speed up this operation in the same way as we  *)
    (* speed up encoding with the private key, below, because that      *)
    (* would require using private information.  This operation may use *)
    (* only key.public and key.n.  In a public key, the other parts of  *)
    (* the key are usually NIL or have meaningless dummy values.        *)

    BEGIN
        RETURN BigNum.ModularPower (m, key.public, key.n);
    END PubKeyEncode;

(************************************************************************)

PROCEDURE Encrypt (m: BN;  key: RSAKeyType): BN;

    (* m is a numerical encoding of the message, with 0 <= M < key.n    *)
    (* We produce a ciphertext using only the public part of the key.   *)

    (* Remark: we cannot speed up encryption in the same way as we      *)
    (* speed up decryption, below, because that would require revealing *)
    (* private information.  Encryption must be done using only the     *)
    (* public key.                                                      *)

    BEGIN
        RETURN PubKeyEncode (m, key);
    END Encrypt;

(************************************************************************)

PROCEDURE SlowDecrypt (c: BN;  key: RSAKeyType): BN;

    (* c is the ciphertext.  We decode it using the private key.  This  *)
    (* is the version to use if we know the private key but not its     *)
    (* (p, q, dp, dq, qinv) components.                                 *)

    BEGIN
        RETURN BigNum.ModularPower (c, key.private, key.n);
    END SlowDecrypt;

(************************************************************************)

PROCEDURE PrivKeyEncode (c: BN;  key: RSAKeyType): BN;

    (* c is the ciphertext.  We encode it using the private key.  This  *)
    (* operation is equivalent to                                       *)
    (*          BigNum.ModularPower (c, key.private, key.n)             *)
    (* but we gain some speed by working with smaller numbers.          *)

    VAR m1, m2, diff, h, hq, Q, R, result: BN;

    BEGIN
        m1 := BigNum.ModularPower (c, key.dp, key.p);
        m2 := BigNum.ModularPower (c, key.dq, key.q);
        diff := BigNum.Diff (m1, m2);
        BigNum.Discard (m1);
        h := BigNum.Prod (key.qinv, diff);
        BigNum.Discard (diff);
        BigNum.Divide (h, key.p, Q, R);
        BigNum.Discard (Q);
        BigNum.Discard (h);
        h := R;
        IF BigNum.Sign(h) < 0 THEN
            result := BigNum.Sum (h, key.p);
            BigNum.Discard (h);
            h := result;
        END (*IF*);
        hq := BigNum.Prod (h, key.q);
        BigNum.Discard (h);
        result := BigNum.Sum (m2, hq);
        BigNum.Discard (m2);
        BigNum.Discard (hq);
        RETURN result;
    END PrivKeyEncode;

(************************************************************************)

PROCEDURE Decrypt (c: BN;  key: RSAKeyType): BN;

    (* c is the ciphertext.  We decode it using the private key.  This  *)
    (* operation is equivalent to                                       *)
    (*          BigNum.ModularPower (c, key.private, key.n)             *)
    (* but we gain some speed by working with smaller numbers.          *)

    BEGIN
        RETURN PrivKeyEncode (c, key);
    END Decrypt;

(************************************************************************)

END RSA.

