Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit06ec1ea

Browse files
committed
Fixsybrenstuvel#162: Blinding uses slow algorithm
Store blinding factor + its inverse, so that they can be reused & updatedon every blinding operation. This avoids expensive computations.The reuse of the previous blinding factor is done via squaring (mod n), asper section 9 of 'A Timing Attack against RSA with the Chinese RemainderTheorem' by Werner Schindler,https://tls.mbed.org/public/WSchindler-RSA_Timing_Attack.pdf
1 parent341e5c4 commit06ec1ea

File tree

3 files changed

+47
-24
lines changed

3 files changed

+47
-24
lines changed

‎CHANGELOG.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,8 @@
77
code
88
- Add padding length check as described byPKCS#1 v1.5 (Fixes
99
[#164](https://github.com/sybrenstuvel/python-rsa/issues/164))
10+
- Reuse of blinding factors to speed up blinding operations.
11+
Fixes[#162](https://github.com/sybrenstuvel/python-rsa/issues/162).
1012

1113

1214
##Version 4.4 & 4.6 - released 2020-06-12

‎rsa/key.py

Lines changed: 32 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -49,12 +49,15 @@
4949
classAbstractKey:
5050
"""Abstract superclass for private and public keys."""
5151

52-
__slots__= ('n','e')
52+
__slots__= ('n','e','blindfac','blindfac_inverse')
5353

5454
def__init__(self,n:int,e:int)->None:
5555
self.n=n
5656
self.e=e
5757

58+
# These will be computed properly on the first call to blind().
59+
self.blindfac=self.blindfac_inverse=-1
60+
5861
@classmethod
5962
def_load_pkcs1_pem(cls,keyfile:bytes)->'AbstractKey':
6063
"""Loads a key in PKCS#1 PEM format, implement in a subclass.
@@ -145,7 +148,7 @@ def save_pkcs1(self, format: str = 'PEM') -> bytes:
145148
method=self._assert_format_exists(format,methods)
146149
returnmethod()
147150

148-
defblind(self,message:int,r:int)->int:
151+
defblind(self,message:int)->int:
149152
"""Performs blinding on the message using random number 'r'.
150153
151154
:param message: the message, as integer, to blind.
@@ -159,10 +162,10 @@ def blind(self, message: int, r: int) -> int:
159162
160163
See https://en.wikipedia.org/wiki/Blinding_%28cryptography%29
161164
"""
165+
self._update_blinding_factor()
166+
return (message*pow(self.blindfac,self.e,self.n))%self.n
162167

163-
return (message*pow(r,self.e,self.n))%self.n
164-
165-
defunblind(self,blinded:int,r:int)->int:
168+
defunblind(self,blinded:int)->int:
166169
"""Performs blinding on the message using random number 'r'.
167170
168171
:param blinded: the blinded message, as integer, to unblind.
@@ -174,8 +177,27 @@ def unblind(self, blinded: int, r: int) -> int:
174177
See https://en.wikipedia.org/wiki/Blinding_%28cryptography%29
175178
"""
176179

177-
return (rsa.common.inverse(r,self.n)*blinded)%self.n
180+
return (self.blindfac_inverse*blinded)%self.n
178181

182+
def_initial_blinding_factor(self)->int:
183+
for_inrange(1000):
184+
blind_r=rsa.randnum.randint(self.n-1)
185+
ifrsa.prime.are_relatively_prime(self.n,blind_r):
186+
returnblind_r
187+
raiseRuntimeError('unable to find blinding factor')
188+
189+
def_update_blinding_factor(self):
190+
ifself.blindfac<0:
191+
# Compute initial blinding factor, which is rather slow to do.
192+
self.blindfac=self._initial_blinding_factor()
193+
self.blindfac_inverse=rsa.common.inverse(self.blindfac,self.n)
194+
else:
195+
# Reuse previous blinding factor as per section 9 of 'A Timing
196+
# Attack against RSA with the Chinese Remainder Theorem' by Werner
197+
# Schindler.
198+
# See https://tls.mbed.org/public/WSchindler-RSA_Timing_Attack.pdf
199+
self.blindfac=pow(self.blindfac,2,self.n)
200+
self.blindfac_inverse=pow(self.blindfac_inverse,2,self.n)
179201

180202
classPublicKey(AbstractKey):
181203
"""Represents a public RSA key.
@@ -414,13 +436,6 @@ def __ne__(self, other: typing.Any) -> bool:
414436
def__hash__(self)->int:
415437
returnhash((self.n,self.e,self.d,self.p,self.q,self.exp1,self.exp2,self.coef))
416438

417-
def_get_blinding_factor(self)->int:
418-
for_inrange(1000):
419-
blind_r=rsa.randnum.randint(self.n-1)
420-
ifrsa.prime.are_relatively_prime(self.n,blind_r):
421-
returnblind_r
422-
raiseRuntimeError('unable to find blinding factor')
423-
424439
defblinded_decrypt(self,encrypted:int)->int:
425440
"""Decrypts the message using blinding to prevent side-channel attacks.
426441
@@ -431,11 +446,9 @@ def blinded_decrypt(self, encrypted: int) -> int:
431446
:rtype: int
432447
"""
433448

434-
blind_r=self._get_blinding_factor()
435-
blinded=self.blind(encrypted,blind_r)# blind before decrypting
449+
blinded=self.blind(encrypted)# blind before decrypting
436450
decrypted=rsa.core.decrypt_int(blinded,self.d,self.n)
437-
438-
returnself.unblind(decrypted,blind_r)
451+
returnself.unblind(decrypted)
439452

440453
defblinded_encrypt(self,message:int)->int:
441454
"""Encrypts the message using blinding to prevent side-channel attacks.
@@ -447,10 +460,9 @@ def blinded_encrypt(self, message: int) -> int:
447460
:rtype: int
448461
"""
449462

450-
blind_r=self._get_blinding_factor()
451-
blinded=self.blind(message,blind_r)# blind before encrypting
463+
blinded=self.blind(message)# blind before encrypting
452464
encrypted=rsa.core.encrypt_int(blinded,self.d,self.n)
453-
returnself.unblind(encrypted,blind_r)
465+
returnself.unblind(encrypted)
454466

455467
@classmethod
456468
def_load_pkcs1_der(cls,keyfile:bytes)->'PrivateKey':

‎tests/test_key.py

Lines changed: 13 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -21,11 +21,20 @@ def test_blinding(self):
2121
message=12345
2222
encrypted=rsa.core.encrypt_int(message,pk.e,pk.n)
2323

24-
blinded=pk.blind(encrypted,4134431)# blind before decrypting
25-
decrypted=rsa.core.decrypt_int(blinded,pk.d,pk.n)
26-
unblinded=pk.unblind(decrypted,4134431)
24+
blinded_1=pk.blind(encrypted)# blind before decrypting
25+
decrypted=rsa.core.decrypt_int(blinded_1,pk.d,pk.n)
26+
unblinded_1=pk.unblind(decrypted)
2727

28-
self.assertEqual(unblinded,message)
28+
self.assertEqual(unblinded_1,message)
29+
30+
# Re-blinding should use a different blinding factor.
31+
blinded_2=pk.blind(encrypted)# blind before decrypting
32+
self.assertNotEqual(blinded_1,blinded_2)
33+
34+
# The unblinding should still work, though.
35+
decrypted=rsa.core.decrypt_int(blinded_2,pk.d,pk.n)
36+
unblinded_2=pk.unblind(decrypted)
37+
self.assertEqual(unblinded_2,message)
2938

3039

3140
classKeyGenTest(unittest.TestCase):

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp