11 #include "RsaCrtShamirsTrick.h"
13 Tests::Tests(uint keySizeBits
, uint rsaPublicExponent
) :
14 KEY_SIZE_BITS(keySizeBits
),
15 RSA_PUBLIC_EXPONENT(rsaPublicExponent
)
19 void Tests::runTests()
21 cout
<< "Tests::runTests() ..." << endl
;
23 cout
<< "RSA standard: " << (this->rsaStandard() ? "OK" : "failed!") << endl
;
24 cout
<< "RSA CRT: " << (this->rsaCrt() ? "OK" : "failed!") << endl
;
27 void Tests::runTestsWithShamirsTrick()
29 cout
<< "Tests::runTestsWithShamirsTrick() ..." << endl
;
31 cout
<< "RSA CRT with Shamir's trick: " << (this->rsaCrtWithShamirsTrick() ? "OK" : "failed!") << endl
;
34 void Tests::runTimeMeasures()
36 cout
<< "Tests::runTimeMeasures() ..." << endl
;
39 const int nbKeys
= 20; // Number of different generated key.
43 int timeRsaCRTShamirsTrick
= 0;
45 for (int k
= 0; k
< nbKeys
; ++k
)
47 timeRsaStd
+= timeSignRsaStd(N
);
48 timeRsaCRT
+= timeSignRsaCRT(N
);
49 timeRsaCRTShamirsTrick
+= timeSignRsaCRTShamirsTrick(N
);
52 cout
<< N
* nbKeys
<< " x RSA standard: " << timeRsaStd
<< " ms" << endl
;
53 cout
<< N
* nbKeys
<< " x RSA CRT: " << timeRsaCRT
<< " ms" << endl
;
54 cout
<< N
* nbKeys
<< " x RSA CRT Shamir's trick: " << timeRsaCRTShamirsTrick
<< " ms" << endl
;
55 cout
<< "Speedup for CRT: " << (double(timeRsaStd
) / double(timeRsaCRT
)) << endl
;
56 cout
<< "Speedup for CRT with Shamir's trick: " << (double(timeRsaStd
) / double(timeRsaCRTShamirsTrick
)) << endl
;
59 void Tests::doAttack()
61 cout
<< "Tests::doAttack() ..." << endl
;
63 const auto& keys
= RsaCrt::generateRSAKeys(RSA_PUBLIC_EXPONENT
, KEY_SIZE_BITS
);
64 const auto& kPub
= keys
.first
;
65 const auto& kPriv
= keys
.second
;
67 mpz_class message
= Rand::randSize(128);
68 mpz_class faultySignature
= RsaCrt::signWithFaultySp(message
, kPriv
);
69 mpz_class correctSignature
= RsaCrt::sign(message
, kPriv
);
71 bool attackSuccessful
= true;
73 cout
<< "Original:" << endl
;
74 cout
<< " p = " << kPriv
.p
<< endl
;
75 cout
<< " q = " << kPriv
.q
<< endl
;
77 // At this point the attacker doesn't know the private key but he has intercepted the message and the faulty signature.
79 mpz_class faultySignaturePowerE
;
80 mpz_pow_ui(faultySignaturePowerE
.get_mpz_t(), faultySignature
.get_mpz_t(), RSA_PUBLIC_EXPONENT
);
81 mpz_class messageMinuxFaultySignaturePowerE
= message
- faultySignaturePowerE
;
83 mpz_gcd(q
.get_mpz_t(), messageMinuxFaultySignaturePowerE
.get_mpz_t(), kPub
.n
.get_mpz_t());
84 mpz_class p
= kPub
.n
/ q
;
86 cout
<< "Found with a faulty signature:" << endl
;
87 cout
<< " p = " << p
<< endl
;
88 cout
<< " q = " << q
<< endl
;
90 attackSuccessful
= attackSuccessful
&& kPriv
.p
== p
&& kPriv
.q
== q
; // With p and q we can recreate the original private key.
93 // Try the attack with a correct signature (p and q shouldn't be found).
95 mpz_class correctSignaturePowerE
;
96 mpz_pow_ui(correctSignaturePowerE
.get_mpz_t(), correctSignature
.get_mpz_t(), RSA_PUBLIC_EXPONENT
);
97 mpz_class messageMinuxCorrectSignaturePowerE
= message
- correctSignaturePowerE
;
99 mpz_gcd(q
.get_mpz_t(), messageMinuxCorrectSignaturePowerE
.get_mpz_t(), kPub
.n
.get_mpz_t());
100 mpz_class p
= kPub
.n
/ q
;
102 cout
<< "Found with a correct signature:" << endl
;
103 cout
<< " p = " << p
<< endl
; // Equal to 1.
104 cout
<< " q = " << q
<< endl
; // Equal to n.
106 attackSuccessful
= attackSuccessful
&& kPriv
.p
!= p
&& kPriv
.q
!= q
;
109 if (attackSuccessful
)
110 cout
<< "Attack successful" << endl
;
112 cout
<< "Attack failed" << endl
;
115 void Tests::doAttackFixed()
117 cout
<< "Tests::doAttackFixed() ..." << endl
;
119 const auto& keys
= RsaCrtShamirsTrick::generateRSAKeys(RSA_PUBLIC_EXPONENT
, KEY_SIZE_BITS
);
120 const auto& kPriv
= keys
.second
;
122 mpz_class message
= Rand::randSize(128);
126 RsaCrtShamirsTrick::signWithFaultySp(message
, kPriv
);
127 cout
<< "Attack successful -> incorrect" << endl
;
129 catch (const RsaCrtShamirsTrick::UnableToSignWithShamirsTrick
& e
)
131 cout
<< "Attack failed -> correct" << endl
;
135 bool Tests::rsaStandard()
137 const auto& keys
= RsaStd::generateRSAKeys(RSA_PUBLIC_EXPONENT
, KEY_SIZE_BITS
);
138 const auto& kPub
= keys
.first
;
139 const auto& kPriv
= keys
.second
;
142 mpz_class message
= kPriv
.n
;
143 mpz_class signature
= RsaStd::sign(message
, kPriv
);
144 if (Rsa::verifySignature(message
, signature
, kPub
)) // Must not be able to signe message greater than kPriv.n.
149 mpz_class message
= kPriv
.n
- 1;
150 mpz_class signature
= RsaStd::sign(message
, kPriv
);
151 if (!Rsa::verifySignature(message
, signature
, kPub
) || Rsa::verifySignature(message
+ 1, signature
, kPub
))
156 mpz_class message
= kPriv
.n
/ 2;
157 mpz_class signature
= RsaStd::sign(message
, kPriv
);
158 if (!Rsa::verifySignature(message
, signature
, kPub
) || Rsa::verifySignature(message
+ 1, signature
, kPub
))
167 const auto& keys
= RsaCrt::generateRSAKeys(RSA_PUBLIC_EXPONENT
, KEY_SIZE_BITS
);
168 const auto& kPub
= keys
.first
;
169 const auto& kPriv
= keys
.second
;
172 mpz_class message
= kPub
.n
;
173 mpz_class signature
= RsaCrt::sign(message
, kPriv
);
174 if (Rsa::verifySignature(message
, signature
, kPub
)) // Must not be able to signe message greater than kPub.n.
179 mpz_class message
= kPub
.n
- 1;
180 mpz_class signature
= RsaCrt::sign(message
, kPriv
);
181 if (!Rsa::verifySignature(message
, signature
, kPub
) || Rsa::verifySignature(message
+ 1, signature
, kPub
))
186 mpz_class message
= kPub
.n
/ 2;
187 mpz_class signature
= RsaCrt::sign(message
, kPriv
);
188 if (!Rsa::verifySignature(message
, signature
, kPub
) || Rsa::verifySignature(message
+ 1, signature
, kPub
))
195 bool Tests::rsaCrtWithShamirsTrick()
197 const auto& keys
= RsaCrtShamirsTrick::generateRSAKeys(RSA_PUBLIC_EXPONENT
, KEY_SIZE_BITS
);
198 const auto& kPub
= keys
.first
;
199 const auto& kPriv
= keys
.second
;
202 mpz_class message
= kPub
.n
;
203 mpz_class signature
= RsaCrtShamirsTrick::sign(message
, kPriv
);
204 if (Rsa::verifySignature(message
, signature
, kPub
)) // Must not be able to signe message greater than kPub.n.
209 mpz_class message
= kPub
.n
- 1;
210 mpz_class signature
= RsaCrtShamirsTrick::sign(message
, kPriv
);
211 if (!Rsa::verifySignature(message
, signature
, kPub
) || Rsa::verifySignature(message
+ 1, signature
, kPub
))
216 mpz_class message
= kPub
.n
/ 2;
217 mpz_class signature
= RsaCrtShamirsTrick::sign(message
, kPriv
);
218 if (!Rsa::verifySignature(message
, signature
, kPub
) || Rsa::verifySignature(message
+ 1, signature
, kPub
))
225 int Tests::timeSignRsaStd(int N
)
228 const auto& keys
= RsaStd::generateRSAKeys(RSA_PUBLIC_EXPONENT
, KEY_SIZE_BITS
);
230 mpz_class message
= Rand::randSize(KEY_SIZE_BITS
/ 2);
231 for (int i
= 0; i
< N
; i
++)
232 RsaStd::sign(message
, keys
.second
);
237 int Tests::timeSignRsaCRT(int N
)
240 const auto& keys
= RsaCrt::generateRSAKeys(RSA_PUBLIC_EXPONENT
, KEY_SIZE_BITS
);
242 mpz_class message
= Rand::randSize(KEY_SIZE_BITS
/ 2);
243 for (int i
= 0; i
< N
; i
++)
244 RsaCrt::sign(message
, keys
.second
);
249 int Tests::timeSignRsaCRTShamirsTrick(int N
)
252 const auto& keys
= RsaCrtShamirsTrick::generateRSAKeys(RSA_PUBLIC_EXPONENT
, KEY_SIZE_BITS
);
254 mpz_class message
= Rand::randSize(KEY_SIZE_BITS
/ 2);
255 for (int i
= 0; i
< N
; i
++)
256 RsaCrtShamirsTrick::sign(message
, keys
.second
);