I’m implementing the RSA cryptosystem for a school project. I’m doing the project in C on Linux and I’m using the GNU MP library for most of the mathematical operations.
For some reason I keep getting the same cyphertext for different public keys with the same message, so either I don’t understand RSA, or there’s something wrong with my code but I can’t figure it out.
Here’s the code in question:
#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>
#include "libs/Crypto/Crypto.h"
#include "libs/Common/common.h"
int RSAkeyGen(mpz_t returnPriKey, mpz_t returnPubKey,long *e, int keySize,int secure)
{
mpz_t prime1,prime2,prime1m1,prime2m1,subResult,minPrimeDiff,keySizeMPZ,gcd,phin;
mpz_init(prime1);
mpz_init(prime2);
mpz_init(prime1m1);
mpz_init(prime2m1);
mpz_init(subResult);
mpz_init(minPrimeDiff);
mpz_init(keySizeMPZ);
mpz_set_ui(keySizeMPZ,keySize);
mpz_init(gcd);
mpz_init(phin);
//chosing e value for RSA, 3 is less secure than 65537
if(secure == 0)
{
*e = 3;
}
else
{
*e = 65537;
}
do
{
//create first prime number
primeGen(prime1,keySize/2,1,secure);
//create second prime number and make sure that |p1-p2|>2*(KeySize)^1/4 so that factorising the prime numbers is hard.
do
{
primeGen(prime2,keySize/2,1,secure);
mpz_sub(subResult,prime1,prime2); //|p1-p2|
mpz_pow_ui(minPrimeDiff,keySizeMPZ,0.25); //(KeySize)^1/4
mpz_mul_ui(minPrimeDiff,minPrimeDiff,2); //2*(KeySize)^1/4
if(mpz_cmp_ui(subResult,0)>0) //make sure that |p1-p2| is positive
{
mpz_mul_ui(subResult,subResult,-1); //check if subResult>subResult
}
}while(mpz_cmp(subResult,minPrimeDiff)>0);
//calculate phi n
mpz_sub_ui(prime1m1,prime1,1);
mpz_sub_ui(prime2m1,prime2,1);
mpz_mul(phin,prime1m1,prime2m1);
//makes sure that the greates common divider of phin is 1
mpz_gcd_ui(gcd,phin,*e);
}while(mpz_cmp_ui(gcd,1)!=0);
//create public key
mpz_mul(returnPubKey,prime1,prime2);
//creates private key
mpz_mul_ui(returnPriKey,phin,2);
mpz_add_ui(returnPriKey,returnPriKey,1);
mpz_div_ui(returnPriKey,returnPriKey,*e);
//clear all values
mpz_clear(prime1);
mpz_clear(prime2);
mpz_clear(prime1m1);
mpz_clear(prime2m1);
mpz_clear(subResult);
mpz_clear(minPrimeDiff);
mpz_clear(keySizeMPZ);
mpz_clear(gcd);
mpz_clear(phin);
return EXIT_SUCCESS;
}
int RSACrypt(mpz_t message, mpz_t pubKey, long e)
{
mpz_powm_ui(message,message,e,pubKey);
return EXIT_SUCCESS;
}
int RSADecrypt(mpz_t message, mpz_t pubKey, mpz_t priKey)
{
mpz_powm(message,message,priKey,pubKey);
return EXIT_SUCCESS;
}
int main()
{
long e;
mpz_t priKey, pubKey,message;
mpz_init(priKey);
mpz_init(pubKey);
mpz_init(message);
mpz_set_ui(message,48);
RSAkeyGen(priKey,pubKey,&e,2048,0);
mpzPrint("pub",pubKey);
mpzPrint("pri",priKey);
printf("%li \n",e);
RSACrypt(message,pubKey,e);
mpzPrint("enc mess",message);
RSADecrypt(message,pubKey,priKey);
mpzPrint("dec mess",message);
mpz_clear(priKey);
mpz_clear(pubKey);
mpz_clear(message);
return EXIT_SUCCESS;
}
This is an example of what i get
➜ AC20_Cyrpto git:(current) ✗ ./Compil
pub= 8818332048526086477764081639060434339035282644546236991358228435742507654168954050081906258726434003763892378384237639654808493250588448618288199793203878440145924620462766904758557330368644247266075972733075192873133021722312342755261391746100364523017679151513503035810521499148896805684061998013984026841009561670642670299045379865518321100760961347918830146555295245932694541598960495007610390917028763723400697323457943767516821373828776866040317216121307849912671324061673115943869961108477391443750826452346780186974189587789564748658752047199187167776120429945604984748162604155876211026689336307380928590793
pri= 5878888032350724318509387759373622892690188429697491327572152290495005102779302700054604172484289335842594918922825093103205662167058965745525466528802585626763949746975177936505704886912429498177383981822050128582088681148208228503507594497400243015345119434342335357207014332765931203789374665342656017893866859734737881161593444600396191838013024282903871741348141772829171807224893237326156437701844578171618227688323796740447791402532829389046553945112004797228714107567736645883912271351395572780263621527160277911947755194673322705937610347874318122294176216651865768535058773668458972697825622668901313197699
3
enc mess= 110592
dec mess= 48
➜ AC20_Cyrpto git:(current) ✗ ./Compil
pub= 4996174516280996279564007291896814196949643804465712074515435065358128922709602225208506081125204805596751688025397767420787172232382909231546630288455805668283065117284833173250978920318159467868351650258245654452490179581729679595403644080218069639078299154165744347591932872624667855911575467160612542831524227760554118843353472032999353056463678667872146897275459403801935884505769648765095357179488080891809217582153069819918155420565659540535831416956639583087891272420960436263397041057293685750580685429949706285595544857832950762880419681100317496854315097793000133052766368090039831181212417398065374901537
pri= 3330783010853997519709338194597876131299762536310474716343623376905419281806401483472337387416803203731167792016931844947191448154921939487697753525637203778855376744856555448833985946878772978578901100172163769634993453054486453063602429386812046426052199436110496231727955248416445237274383644773741695220908949765869769400317933032145817117523206556511477046841246962936557741276509304880716544681382973925453792737820599739468894922534059877253319346713443800216586965522952903664046603287700839868003149135244796106781682697270074276434201477924023573422173494286385123720123134875205052647947365348452779822691
3
enc mess= 110592
dec mess= 48
➜ AC20_Cyrpto git:(current) ✗ ./Compil
pub= 8324895762755374719600833678337875891021624217848902406381326762646587891283129777940102014356942506526531643992869683512498071843564601512854099050019846948695251133775752053749717714362249293797195573359778512324630165324715372189091402711502878233769832695795558266455911323818283676348078713363881904497647036230589561813786200714989798046772944910196261963241104912485955524226787283312675738918145150030866986238569663121839029032979265131683720126814431960037637344127763242024962143824578243845713574312394247375374086003661946215884036605135832424877593681142320283320160990970605974170620663199160628361481
pri= 5549930508503583146400555785558583927347749478565934937587551175097725260855419851960068009571295004351021095995246455674998714562376401008569399366679897965796834089183834702499811809574832862531463715573185674883086776883143581459394268474335252155846555130530372177637274215878855784232052475575921269664973946560507623872295980300888226622173830400983227267749109919171377398967395487402997262830689787121841629426434862730841394641079893594575852450282265989726326281757366298263995847846451863391143005475184142355114146955124141693914763349106750505537122160903782124321725947053774613472265362452299151149067
3
enc mess= 110592
dec mess= 48
48 to the 3rd is always 110592. 110592 mod (big number) is 110592.
The RSA primitives are not a secure algorithm. In order to effectively hide the input for encryption you need to guarantee that the "message" value raised to the power of the public exponent actually exceeds the modulus.
The way that this is accomplished is called padding. All four padding families for RSA set a bit in the second-most-significant byte to guarantee that a) any exponentiation of that value will exceed the modulus and b) that the padded value itself does not exceed the modulus (which is why it's not the most-significant-byte). Then you apply the RSA primitive to the padded message instead of the original message, and now a secure system can be born.
(4 families? RSA PKCS#1 v1.5 encryption, RSA PKCS#1 v1.5 signature, RSA-OAEP, RSA-PSS)