rsacrypt.h

Go to the documentation of this file.

/*
**  Command & Conquer Generals Zero Hour(tm)
**  Copyright 2025 Electronic Arts Inc.
**
**  This program is free software: you can redistribute it and/or modify
**  it under the terms of the GNU General Public License as published by
**  the Free Software Foundation, either version 3 of the License, or
**  (at your option) any later version.
**
**  This program is distributed in the hope that it will be useful,
**  but WITHOUT ANY WARRANTY; without even the implied warranty of
**  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
**  GNU General Public License for more details.
**
**  You should have received a copy of the GNU General Public License
**  along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
 
#ifndef RSACRYPT_H
#define RSACRYPT_H
 
#include <wwlib/int.h>
#include <wwlib/wwfile.h>
 
//#define SIMPLE_AND_SLOW_RSA
 
// Version identification string for OpenSSH identity files.
#define AUTHFILE_ID_STRING "SSH PRIVATE KEY FILE FORMAT 1.1\n"
 
//
// RSACrypt - Implementation of RSA using the Int class from wwlib
//
// For key generation I suggest you use OpenSSH (http://www.openssh.com/)
// There is a utility called "ssh-keygen", call:
//
// ssh-keygen [-b bits]
//
// If you generate the file on a UNIX system, be sure and FTP it in BINARY MODE!!!!
//
// You can then use 'Load_SSH_Keyset' on the identity file it produces.
//
// Note: Make sure you leave the keyphrase blank for the SSH keyset.  I don't support
//   decrypting that file!
//
// Notation:
// Public keys:
//  n = product of two primes, p & q (p & q must remain secret)
//  e = relatively prime to (p-1)(q-1)
// 
// Private keys:
//  d = e^-1 mod ((p-1)(q-1))       // e^-1 = inverse of e
//
// Encrypting:
// cyphertext = m^e mod n
//
// Decrypting:
// message = cyphertext^d mod n
//
// Note: I use a trick involving the chinese remainder theorem to get a 3x speedup in decryption.
// It's well documented on the web so I won't get into detail here.
//
template <int PRECISION>
class RSACrypt
{
 public:
        typedef Int<PRECISION>    Integer;
 
        RSACrypt()  {}
        ~RSACrypt()    {}
 
        void Set_Public_Keys(const Integer &pub_n, const Integer &pub_e);
        void Set_Keys(const Integer &pub_n, const Integer &pub_e, 
            const Integer &priv_d, const Integer &keygen_p, const Integer &keygen_q);
 
        void Get_Public_Keys(Integer &pub_n, Integer &pub_e) const;
        void Get_Private_Key(Integer &priv_d) const;
        void Get_Keygen_Keys(Integer &keygen_p, Integer &keygen_q) const;
 
        bool Load_SSH_Keyset(FileClass *file);
 
        void Encrypt(const Integer &plaintext, Integer &cyphertext) const;
        void Decrypt(const Integer &cyphertext, Integer &plaintext) const;
 
 private:
        bool Load_Bignum(FileClass *file, Integer &num);
 
        void Decryption_Setup();        // Do precomputation to speedup decryption
 
        Integer      PublicN;
        Integer      PublicE;
 
        Integer      PrivateD;
 
        Integer      KeygenP;        // Primes P & Q generated as part of the keyset
        Integer      KeygenQ;
 
                                        // Precomputed values that speed up encryption
        Integer      DmodPm1;        // d mod p-1
        Integer      DmodQm1;        // d mod q-1
 
        Integer      RP;         // RP = q^(p-1) mod n
        Integer      RQ;         // RQ = p^(q-1) mod n;
};
 
//
// Set the two public keys: n & e
//
template <int PRECISION>
void RSACrypt<PRECISION>::Set_Public_Keys(const Integer &pub_n, const Integer &pub_e)
{
    PublicN=pub_n;
    PublicE=pub_e;
}
 
//
// Set the public & private keys: n, e & d
//
template <int PRECISION>
void RSACrypt<PRECISION>::Set_Keys(const Integer &pub_n, const Integer &pub_e, 
    const Integer &priv_d, const Integer &keygen_p, const Integer &keygen_q)
{
    PublicN=pub_n;
    PublicE=pub_e;
    PrivateD=priv_d;
 
    KeygenP=keygen_p;
    KeygenQ=keygen_q;
 
    Decrtyption_Setup();
}
 
//
// Get the public keys
//
template <int PRECISION>
void RSACrypt<PRECISION>::Get_Public_Keys(Integer &pub_n, Integer &pub_e) const
{
    pub_n=PublicN;
    pub_e=PublicE;
}
 
//
// Get the private key
//
template <int PRECISION>
void RSACrypt<PRECISION>::Get_Private_Key(Integer &priv_d) const 
{
    priv_d=PrivateD;
}
 
 
//
// Get the private numbers created during the keyset generation
// Private as in revealing these will reveal the private key!
//
template <int PRECISION>
void RSACrypt<PRECISION>::Get_Keygen_Keys(Integer &keygen_p, Integer &keygen_q) const
{
    keygen_p=KeygenP;
    keygen_q=KeygenQ;
}
 
 
//
// Load an RSA private keyset from an OpenSSH "identity" file.
//
template <int PRECISION>
bool RSACrypt<PRECISION>::Load_SSH_Keyset(FileClass *file)
{
    assert(file);
    if ( ! file)
        return(false);
 
    bool retval=true;
    unsigned char buffer[1024];
 
    if ( ! file->Open())
        return(false);
 
    file->Read(buffer, strlen(AUTHFILE_ID_STRING)+1);
    buffer[strlen(AUTHFILE_ID_STRING)]=0; // null term
 
    if (strcmp((char *)buffer, AUTHFILE_ID_STRING))
        return(false);
 
    unsigned char cypher_type;      // keyfile encryption method
    file->Read(&cypher_type, 1);
    if (cypher_type != 0)
        return(false);
 
    file->Read(buffer, 4);      // reserved data
 
    file->Read(buffer, 4);      // ignored
 
    retval=retval && Load_Bignum(file, PublicN);
    retval=retval && Load_Bignum(file, PublicE);
    if (!retval)
        return(false);
 
    // comment string
    int comment_length;
    file->Read(&comment_length, 4);
    comment_length=ntohl(comment_length);
 
    file->Read(buffer, comment_length);
 
    // post-decrypt check chars
    file->Read(buffer, 4);
    if ((buffer[0] != buffer[2]) || (buffer[1] != buffer[3]))
        return(false);
 
    Integer q_inv_mod_p; // invserse of q mod p (we don't need this)
 
    retval=retval && Load_Bignum(file, PrivateD);
    retval=retval && Load_Bignum(file, q_inv_mod_p);
    retval=retval && Load_Bignum(file, KeygenP);
    retval=retval && Load_Bignum(file, KeygenQ);
    if (!retval)
        return(false);
 
    // Any remaining bytes are padding
 
    Decryption_Setup();
 
    return(true);
}
 
//
// Precomputation for fast decryption
//
template <int PRECISION>
void RSACrypt<PRECISION>::Decryption_Setup(void)
{
    Integer temp;
 
    // If p < q, swap p & q
    if (KeygenP < KeygenQ)
    {
        temp=KeygenP;
        KeygenP=KeygenQ;
        KeygenQ=temp;
    }
 
    assert(KeygenP > KeygenQ);
 
    // pm1 = p - 1
    Integer pm1(KeygenP);
    --pm1;
 
    // pm1 = p - 1
    Integer qm1(KeygenQ);
    --qm1;
 
    // DmodPm1 = d mod (p-1)
    Integer::Unsigned_Divide(DmodPm1, temp, PrivateD, pm1);
    assert(DmodPm1 < pm1);
 
    // DmodQm1 = d mod (q-1)
    Integer::Unsigned_Divide(DmodQm1, temp, PrivateD, qm1);
    assert(DmodQm1 < qm1);
 
    RP = KeygenQ.exp_b_mod_c(pm1, PublicN);
    RQ = KeygenP.exp_b_mod_c(qm1, PublicN);
}
 
 
//
// RSA Encryption       c = m^e mod n
//
template <int PRECISION>
void RSACrypt<PRECISION>::Encrypt(const Integer &plaintext, Integer &cyphertext) const 
{
    Integer m(plaintext);
    cyphertext=m.exp_b_mod_c(PublicE, PublicN);
}
 
 
//
// RSA Decryption       m = c^d mod n
//
template <int PRECISION>
void RSACrypt<PRECISION>::Decrypt(const Integer &cyphertext, Integer &plaintext) const 
{
#ifdef SIMPLE_AND_SLOW_RSA
    Integer c(cyphertext);
    plaintext=c.exp_b_mod_c(PrivateD, PublicN);
#else
    Integer temp;
 
    // Get a version of the cyphertext mod q & p
    Integer cmp, cmq;
    Integer::Unsigned_Divide(cmp, temp, cyphertext, KeygenP);
    Integer::Unsigned_Divide(cmq, temp, cyphertext, KeygenQ);
 
    // mp = cmp ^ dmp mod p
    Integer mp;
    mp=cmp.exp_b_mod_c(DmodPm1, KeygenP);
 
    // mq = cmq ^ dmq mod q
    Integer mq;
    mq=cmq.exp_b_mod_c(DmodQm1, KeygenQ);
 
 
    Integer  sp, sq;
 
    //sp=mp * RP mod n;
    //sq=mq * RQ mod n;
    XMP_Prepare_Modulus(&PublicN.reg[0], PRECISION);
    XMP_Mod_Mult(&sp.reg[0], &mp.reg[0], &RP.reg[0], PRECISION);
    XMP_Mod_Mult(&sq.reg[0], &mq.reg[0], &RQ.reg[0], PRECISION);
    XMP_Mod_Mult_Clear(PRECISION);
 
    plaintext = sp+sq;
    if (plaintext >= PublicN)
        plaintext-=PublicN;
 
#endif
}
 

 
//
// Load a large number from the SSH keyset file
//
template <int PRECISION>
bool RSACrypt<PRECISION>::Load_Bignum(FileClass *file, Integer &num)
{
    int readlen;
    unsigned char buffer[1024];
    unsigned short int n_bits, n_bytes;
 
    readlen=file->Read(&n_bits, 2);     // bits in network byte order
    if (readlen != 2)
        return(false);
    n_bits=ntohs(n_bits);
    n_bytes=(n_bits+7)/8;
 
    readlen=file->Read(buffer, n_bytes);
    if (readlen != n_bytes)
        return(false);
 
    num.Unsigned_Decode(buffer, n_bytes);
 
    return(true);
}
 
 
#endif