教科书 RSA 相同的密文，不同的密钥
Textbook RSA Same cyphertext with different keys
我正在为一个学校项目实施 RSA 密码系统。我在 Linux 上用 C 语言做这个项目，我使用 GNU MP 库进行大部分数学运算。
出于某种原因，对于具有相同消息的不同 public 密钥，我总是得到相同的密文，所以要么我不理解 RSA，要么我的代码有问题但我无法理解出。
这是有问题的代码：
#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;
}
这是我得到的例子
➜ 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 到第 3 总是 110592。110592 mod（大数）是 110592。
RSA 原语不是安全算法。为了有效地隐藏加密输入，您需要保证 "message" 值的 public 指数次方实际上超过 modulus。
完成此操作的方法称为填充。 RSA 的所有四个填充系列都在第二个最重要的字节中设置了一个位，以保证 a) 该值的任何指数将超过 modulus 和 b) 填充值本身不超过 modulus（这就是为什么它不是最重要的字节）。然后你将RSA原语应用于填充后的消息而不是原始消息，现在可以诞生一个安全系统。
（4 个系列？RSA PKCS#1 v1.5 加密、RSA PKCS#1 v1.5 签名、RSA-OAEP、RSA-PSS）
我正在为一个学校项目实施 RSA 密码系统。我在 Linux 上用 C 语言做这个项目，我使用 GNU MP 库进行大部分数学运算。
出于某种原因，对于具有相同消息的不同 public 密钥，我总是得到相同的密文，所以要么我不理解 RSA，要么我的代码有问题但我无法理解出。
这是有问题的代码：
#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;
}
这是我得到的例子
➜ 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 到第 3 总是 110592。110592 mod（大数）是 110592。
RSA 原语不是安全算法。为了有效地隐藏加密输入，您需要保证 "message" 值的 public 指数次方实际上超过 modulus。
完成此操作的方法称为填充。 RSA 的所有四个填充系列都在第二个最重要的字节中设置了一个位，以保证 a) 该值的任何指数将超过 modulus 和 b) 填充值本身不超过 modulus（这就是为什么它不是最重要的字节）。然后你将RSA原语应用于填充后的消息而不是原始消息，现在可以诞生一个安全系统。
（4 个系列？RSA PKCS#1 v1.5 加密、RSA PKCS#1 v1.5 签名、RSA-OAEP、RSA-PSS）