Voici un exemple d'exécution de l'algorithme RSA :
[klaus@localhost rsa]$ make run ./rsa Begin key generation... Public key = (183, 2173) Private key = (807, 2173) type your message : abcde ciphered message is : 431475187519 Your message is abcde
Le mot saisi est "abcde", que l'on convertit en valeur numérique comme
une suite de valeurs ASCII formant un nombre en base 256. De la même
façon que
. Les codes ASCII de 
,
, 
, 
et 
sont respectivement 
, 
, 
, 
et
. On forme le nombre suivant
. Il est plus simple algorithmiquement de
construire 
en lisant les nombres de la chaîne à l'envers,
c'est-à-dire en considérant que le 'a' est le caractère de poids
faible et le 'e' le caractère de poids fort. On remarque que la clé
publique est
et que 
. Il convient de
découper en le décomposant en base 
, c'est-à-dire en
l'exprimant de la sorte :
. On a donc
blocs à chiffrer
. On obtient ainsi les blocs
. On termine le chiffrement en donnant le nombre
représenté par 
(comme avant, poids faible sur 
) en
base . Soit
. Le déchiffrement s'effectue exactement de la même
façon.
#include<stdio.h>
#include<gmp.h>
#define LIMIT_EXP 50
#define NB_TRIALS 100
#define NB_BLOCKS 100
#define BASE 256
#define MSG_SIZE 5000
#define CLEAR_BUFFER while(getchar() != '\n')
/********************************************************************/
/*
Tous les parametres des fonctions doivent etre initialises (alloues)
avant l'appel de la fonction. Sauf les cellules des tableaux
qui peuvent l'etre pendant l'execution de la fonction.
*/
/********************************************************************/
/********************************************************************/
/********************************************************************/
/*
Chiffre l'entier message avec la cle (exp, modulus),
place le resultat dans ciphered.
*/
void encrypt(mpz_t ciphered, mpz_t message, mpz_t exp, mpz_t modulus)
{
}
/********************************************************************/
/*
Verifie que a^(modulus - 1) mod modulus = 1.
*/
int checkFermat(mpz_t a, mpz_t modulus)
{
return 0;
}
/********************************************************************/
/*
Retourne vrai si et seulement si en prenant nbTrials valeurs de a,
on a a^(n-1) mod n = 1.
*/
int isProbablyPrime(mpz_t n, int nbTrials)
{
return 0;
}
/********************************************************************/
/*
Genere un nombre premier, verifie sa primarite avec
isProbablyPrime.
*/
void generatePrime(mpz_t primeNumber)
{
}
/********************************************************************/
/*
Genere un nombre modulus, produit de deux nombres premiers p et q.
Affecte a phi l'indicatrice d'Euler de modulus.
*/
void generateModulus(mpz_t modulus, mpz_t phi)
{
}
/********************************************************************/
/*
Saisit une chaine d'au plus maxSize caracteres,
la place dans message.
*/
void getMessage(char* message, int maxSize)
{
int i;
printf("type your message : \n");
fgets(message, maxSize, stdin);
i = 0;
while(message[i] != 0)
i++;
if (i > 0 && message[i-1] != '\n')
CLEAR_BUFFER;
else
message[i-1] = 0;
}
/********************************************************************/
/*
Affiche la chaine de caracteres message sur stdout.
*/
void printMessage(char* message)
{
printf("Your message is \n%s\n", message);
}
/********************************************************************/
/*
Genere un exposant de chiffrement premier avec phi,
le place dans encryptExp.
*/
void generateEncryptExp(mpz_t encryptExp,
mpz_t phi)
{
}
/********************************************************************/
/*
Genere l'exposant de dechiffrement correspondant a l'exposant
de chiffrement encryptExp. Le place dans decryptExp.
*/
void generateDecryptExp(mpz_t encryptExp,
mpz_t decryptExp,
mpz_t phi)
{
}
/********************************************************************/
/*
Genere un couple d'exposants encryptExp et decryptExp correspondants
au module dont l'indicatrice d'Euler est phi.
*/
void generateExponents(mpz_t encryptExp,
mpz_t decryptExp,
mpz_t phi)
{
generateEncryptExp(encryptExp, phi);
generateDecryptExp(encryptExp, decryptExp, phi);
}
/********************************************************************/
/*
Genere un couple cle publique/cle privee.
*/
void generateKeys(mpz_t encryptExp,
mpz_t decryptExp,
mpz_t n)
{
mpz_t phi;
mpz_init(phi);
printf("Begin key generation...\n");
gmp_randinit_mt(state);
generateModulus(n, phi);
generateExponents(encryptExp, decryptExp, phi);
printf("Public key = (");
mpz_out_str(NULL, 10, encryptExp);
printf(", ");
mpz_out_str(NULL, 10, n);
printf(")\nPrivate key = (");
mpz_out_str(NULL, 10, decryptExp);
printf(", ");
mpz_out_str(NULL, 10, n);
printf(")\n");
mpz_clear(phi);
gmp_randclear(state);
}
/********************************************************************/
/*
Convertit le nombre mpzMsg en base modulus, place les chiffres dans
clearMsgBlocks. Les nombres de poids faible sont places au debut.
Retourne le nombre d'elements places dans clearMsgBlocks.
*/
int splitMessage(mpz_t* clearMsgBlocks, mpz_t mpzMsg, mpz_t modulus)
{
return 0;
}
/********************************************************************/
/*
Calcule le nombre ecrit en base modulus dans le tableau
clearMsgBlocks. Place le resultat dans clearMsg.
Les chiffres sont disposes a l'envers dans clearMsgBlocks : ceux
de poids faible sont au debut.
*/
void unSplitMessage(mpz_t clearMsg,
mpz_t* clearMsgBlocks,
mpz_t modulus, int nb)
{
}
/********************************************************************/
/*
Convertit le nombre stocke en base BASE dans la chaine clearMsg,
en un entier. Place le resultat dans mpzMsg. Les chiffres sont places
a l'envers dans clearMsg.
*/
void mpzOfMsg(mpz_t mpzMsg, char* clearMsg)
{
}
/********************************************************************/
/*
Convertit en base BASE le nombre mpzMsg. Place les valeurs
a l'envers dans la chaine clearMsg. Sans oublier le caractere
nul...
*/
void msgOfMpz(char* clearMsg, mpz_t mpzMsg)
{
}
/********************************************************************/
/*
Affiche les nb nombres du tableau clearMsgBlocks.
*/
void printBlocks(mpz_t* clearMsgBlocks, int nb)
{
if (nb > 0)
{
mpz_out_str(NULL, 10, *clearMsgBlocks);
printf(" ");
printBlocks(clearMsgBlocks + 1, nb - 1);
}
else
printf("\n");
}
/********************************************************************/
/*
Chiffre les nb elements de clearMsgBlocks avec la cle
(encryptExp, modulus).
*/
void encryptBlocks(mpz_t* clearMsgBlocks, int nb,
mpz_t encryptExp, mpz_t modulus)
{
}
/********************************************************************/
/*
Chiffre le message clearMsg avec la cle (encryptExp, modulus),
place le resultat dans ciphered.
*/
void encryptMsg(mpz_t ciphered, char* clearMsg, mpz_t encryptExp, mpz_t modulus)
{
}
/********************************************************************/
/*
Dechiffre le message ciphered avec la cle (decryptExp, modulus),
place le resultat dans clearMsg.
*/
void decryptMsg(char* clearMsg, mpz_t ciphered, mpz_t decryptExp, mpz_t modulus)
{
}
/********************************************************************/
/*
Saisit un texte, le chiffre et le dechiffre.
*/
void runRSA()
{
mpz_t modulus, encryptExp, decryptExp, ciphered;
char clearMsg[MSG_SIZE];
char newMsg[MSG_SIZE];
mpz_init(modulus);
mpz_init(ciphered);
mpz_init(encryptExp);
mpz_init(decryptExp);
generateKeys(encryptExp, decryptExp, modulus);
getMessage(clearMsg, MSG_SIZE);
encryptMsg(ciphered, clearMsg, encryptExp, modulus);
printf("ciphered message is :\n");
mpz_out_str(NULL, 10, ciphered);
printf("\n");
decryptMsg(newMsg, ciphered, decryptExp, modulus);
printMessage(newMsg);
mpz_clear(encryptExp);
mpz_clear(decryptExp);
mpz_clear(modulus);
mpz_clear(ciphered);
}
/********************************************************************/
int main(int argv, char** argc)
{
runRSA();
return 0;
}