Image for post
Image for post

How Do I Calculate 5¹²⁸ in eight easy steps?

The answer is:

293,873,587,705,571,876,992,184,134,305,561,419,454,666,389,193,021,880,377,187,926,569,604,314,863,681,793,212,890,625 [here], and I did it in eight mathematical operations.

A recent paper showed that it is possible to determine the private key of RSA by simply listening to the radio waves emitted from a mobile phone. This is because the RSA method uses multiplication and square operations, and which can be observed as the processor consumes different amounts of electrical power as it performs the calculation.

In RSA we decrypt by taking the cipher, and then raising it to the power of d:

Message=Cipher^d (mod N)

and where N is the multiplication of two prime numbers. Our decryption key is (d,N). Thus if we find d, we crack RSA. We know N, as the public key is (e,N).

In order to perform the exponent operation (Cipher^d), we normally use the square and multiply method. So 5⁴ (where 4 is the exponent) becomes:

5² = 25
25²= 625

If we can to multiply 5⁸ that is 5² squared to give 5⁴, and then if we square again we get 5⁸. It has thus taken us three operations to find a power of 8. For 5⁶⁴, we will need six operations:

5²→5⁴→5⁸→5¹⁶→5³²→5⁶⁴

But lets say we want 5⁹. For this we square as we did before to give us 5⁸, and then just multiply by 5 to give 5⁹.

The basic method involves converting the exponent into bits, and then multiplying and squaring if the bit is a ‘1’ (or a power of two), or square if it is a ‘0’. In Python this becomes:

def exp_func(x, y):
exp = bin(y)
value = x

for i in range(3, len(exp)):
value = value * value
print i,":\t",value
if(exp[i:i+1]=='1'):
value = value*x
print i,"*:\t",value
return value

So, with an exponent is 12 we have a binary value of 1100. We ignore the first bit, and start on the ‘1’ (1100) , where we multiply and square. Next we have a ‘0’ (1100), so we just square, and finally a ‘0’ (1100), so we again just square. If we want to raise 5¹², we square(5²) and multiply (5³), next square (5⁶) , next square (5¹²):

Binary value of b is: 0b1100
Bit Result
2 : 25 (square)
2 : 125 (multiply)
3 : 15625 (square)
4 : 244140625 (square)
Result: 244140625

If we try 5¹²⁸ we get [here]:

We will calculate a^b
a= 5
b= 128
==== Calculation ====
Binary value of b is: 0b10000000
Bit Result
2 : 25 (square)
3 : 625 (square)
4 : 390625 (square)
5 : 152587890625 (square)
6 : 23283064365386962890625 (square)
7 : 542101086242752217003726400434970855712890625 (square)
8 : 293873587705571876992184134305561419454666389193021880377187926569604314863681793212890625 (square)
Result: 293873587705571876992184134305561419454666389193021880377187926569604314863681793212890625
===========

And now we can look at a power trace from a device. In this case we see that the SM (Square and Multiply) method takes longer than the S (Square method):

Image for post
Image for post
Power trace [1]

And so we just read of the bits:

0 (S), 1(SM), 1(SM), 0(S), 1SM , 0(S), 0(S), 1(SM), 1(SM), 1(SM), 0(S), 1(SM). We have now revealed virtually all of the bits in the key:

1 011010011101

You must now be worried if you have an embedded device, that you will reveal the decryption key. The safe guard is to put in dummy multiplication operations at random, so that they processor performs operations which do not actually affect the calculation.

If you are interested, here is the code to perform the operation:

import sysa=8
b=5
def exp_func(x, y):
exp = bin(y)
print "Binary value of b is:",exp
print "Bit\tResult"
value = x

for i in range(3, len(exp)):
value = value * value
print i-1,":\t",value,"(square)"
if(exp[i:i+1]=='1'):
value = value*x
print i-1,":\t",value,"(multiply)"
return value
print "We will calculate a^b"
print "a=",a
print "b=",b
print "==== Calculation ===="
res=exp_func(a,b)
print "Result:",res
print "==========="

The operations on the process will also emit radio waves. The faster we run the process, the strong the current in the wires and on the chip, and the more electromagnetic waves that a device will emit.

If you want to read how we can detect the RSA decryption key with radio wave, read this:

A presentation is here [slides]:

[1] Understanding Cryptography: A textbook for students, Page 197.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store