RSA decryption exponent d (c++)
TJakobsen
I am working on a small RSA encryption/decryption program in a school
project (using c++) and I'm kind of stuck because i can't figure out
how to calculate the decryption exponent d.
Keep in mind that my program doesn't use very large primes - it's sort
of a bit simplified in this respect.
My main problem revolves around how to implement a calculation of d in
my program. I can't figure out how to code this. According to various
sources i've used, d is calculated like this:
d = e^-1 (mod phi(n))
As far as I have been able to find out this means that
d mod phi(n) = e^-1 mod phi(n)
But as im not that experienced in advanced mathematics i don't really
know if this is true.
Anyway can anyone explain to me how i calculate d using c++ code or
just in plain easy-to-understand mathematics?
I have used the following numbers:
p = 37
q = 89
n = p*q = 37*89 = 3293
phi(n) = (p-1)(q-1) =3168
e = 25
thx in advance :)
TJakobsen
Ray
Algorithm.
If you google for it, you find plenty of info about it.
For example, start on www.Wikipedia.com
Kind regards
Kristian Gjųsteen
>According to various
>sources i've used, d is calculated like this:
>
>d = e^-1 (mod phi(n))
>
>just in plain easy-to-understand mathematics?
Your equation says that d should be an inverse of e modulo phi(n).
First, you need to understand what an inverse is. This is easy: a is
an inverse of b modulo n iff a times b is congruent to 1 modulo n.
For example: 3 is an inverse of 7 modulo 20 because
3*7 = 21 = 1 (mod 20).
Second, you need to understand how to calculate an inverse of a
number modulo a modulus. The hint is to use the extended Euclidian
algorithm. The basic idea is: You want to find an inverse of the
number x modulo a modulus n. If you can find integer solutions s
and t to the equation
sx + tn = 1
then it is easy to show that s is an inverse of x modulo n.
--
Kristian Gjųsteen
TJakobsen
as im only a high school student (last year though). We don't have
advanced mathematics yet and we haven't really worked with any of the
mathematics related to RSA such as modulo etc.
could someone be so kind as to go through this Extended Euclidian
algorithn using the numbers i've used in my program please?
so we can calculate d.
thanks in advance.
TJakobsen
bert
> I have used the following numbers:
> p = 37
> q = 89
> n = p*q = 37*89 = 3293
> phi(n) = (p-1)(q-1) =3168
> e = 25
3168 / 25 = 126 remainder 18
25 / 18 = 1 remainder 7
18 / 7 = 2 remainder 4
7 / 4 = 1 remainder 3
4 / 3 = 1 remainder 1
Now build up the inverse from (126, 1, 2, 1, 1) like this:
a0 = 0, a1 = 1, a2 = 126 * a1 + a0, a3 = 1 * a2 + a1,
a4 = 2 * a3 + a2, . . .
a0 = 1, a1 = 1, a2 = 126, a3 = 127, a4 = 380, a4 = 507,
a5 = 887. See how, for each n, 25 * a_n mod 3168 is
related to the remainders in the first sequence. To get
the correct inverse in this case we have to go back to
the division sequence and add "3 / 1 = 2 remainder 1"
to get a6 = 2281, which is the required d.
--
Kristian Gjųsteen
>could someone be so kind as to go through this Extended Euclidian
>algorithn using the numbers i've used in my program please?
No. But if you're not willing to look for a description of EE on
your own, find the Handbook of Applied Cryptography on the web and
use Algorithm 2.107.
--
Kristian Gjųsteen
mm
All those who answered you are right, you _should_ use the Euclidean
algorithm, but, since the numbers you are using are very small, you
also can find the needed inverse with an exhaustive search, i.e.,
for i := 1 to PhiN-1 do
if ((i * e) mod PhiN) = 1 then
begin
d := i;
Break;
end;
mm
rossum
As well as Kristian's suggestion of finding the Handbook of Applied
Cryptography, you can also get "A Computational Introduction to Number
Theory and Algebra" by Shoup free on the web, which covers more of the
mathematical background though less of the cryptography. The Extended
Euclidian algorithm is in section 4.2. Wikipedia and Mathworld will no
doubt also have explanations. Google is your friend.
You could also search libraries for "The Art of Computer Programming"
by Knuth in three volumes, you want Volume Two, algorithm 4.5.2X.
Alternatively "Prime Numbers - A Computational Perspective" by Crandall
and Pomerance has the Extended Euclidian algorithm as algorithm 2.1.4.
rossum
Carlos Moreno
I was going to suggest that -- the reason is that I wonder if, being
someone in high school level, if it is a homework, then I estimate
that maybe *this* is precisely what is expected -- find the inverse
by trying all the possible numbers in the range.
Also, if he's doing it for fun, it does make sense to begin with
this simplified version of the problem -- then, for further fun, he
could go with the implementation of the extended Euclidean to find
the inverse.
Carlos
--
Timo Johansson
TJakobsen wrote:
>d is calculated like this:
>
> d = e^-1 (mod phi(n))
d = e^{-1} = e^{phi(n)-1} (mod phi(n))
since phi(n) = 0 (mod phi(n))
> I have used the following numbers:
>
> p = 37
> q = 89
> n = p*q = 37*89 = 3293
> phi(n) = (p-1)(q-1) =3168
> e = 25
So, maybe it's more simple for you to compute
e^{phi(n)-1} = 25^3167
The result is a quite huge number, but you can use modulo reduction after
every multiplication:
unsigned long int d,e;
int i;
e=25;
d=25;
for(i=0;i<3168-1;i++){
d *= e;
d %= 3168;
}
although i'd prefer using the extended euclidean alg...!
Remark, this is a quick shot and not tested, so I'm almost shure there are a
few mistakes, but I guess you got the idea of what I mean...
regards, Timo
Mike Amling
Perhaps you can translate this Java into your C++.
long inverse(long ee, long mm) {
if (ee<=1) {
if (ee==1) {
return 1;
}
throw new IllegalArgumentException(
"ee must be >=1, not "+ee);
}
// If we can find ss and tt such that
// ss*ee+tt*mm=1
// then ss would be the inverse of ee modulo mm. We
// could return ss=(1-tt*mm)/ee or, even better,
// (1-tt*mm)/ee+mm, which is >=1.
// When we take the equation ss*ee+tt*mm=1 modulo
// ee, it becomes
// tt*mm==1 mod ee,
// so one value that would work for tt is the inverse
// of mm modulo ee.
return (1-inverse(mm%ee, ee)*mm)/ee+mm;
}
--Mike Amling
Unruh
>Hello,
>TJakobsen wrote:
>>d is calculated like this:
>>
>> d = e^-1 (mod phi(n))
>d = e^{-1} = e^{phi(n)-1} (mod phi(n))
>since phi(n) = 0 (mod phi(n))
>> I have used the following numbers:
>>
>> p = 37
>> q = 89
>> n = p*q = 37*89 = 3293
>> phi(n) = (p-1)(q-1) =3168
>> e = 25
>So, maybe it's more simple for you to compute
>e^{phi(n)-1} = 25^3167
>The result is a quite huge number, but you can use modulo reduction after
>every multiplication:
>unsigned long int d,e;
>int i;
>e=25;
>d=25;
>for(i=0;i<3168-1;i++){
> d *= e;
> d %= 3168;
>}
3167=110001011111
e^3167= e*(e^2)(e^2^2)(e^2^2^2)(e^2^2^2^2)(e^2^2^2^2^2^2).....
(e^2^2=(e^2)^2
Ie, You can claculate the squares of e and its squares and then multiply
them together. This is only 12 squarings and 8 multiplication (modulo
reducing each one) (ie 20 multiplications and modulo reductions) rather
than 3167 of them.
z=e;
d=1;
p=3167;
for(i=1;i<=12;i++)
{
if((p%2) == 1) d=(d*z)%3167;
p/=2;
z=(z*z)%3167;
}
>although i'd prefer using the extended euclidean alg...!
>Remark, this is a quick shot and not tested, so I'm almost shure there are a
>few mistakes, but I guess you got the idea of what I mean...
Similarly.
>regards, Timo
Kristian Gjųsteen
>TJakobsen wrote:
>>d is calculated like this:
>>
>> d = e^-1 (mod phi(n))
>
>d = e^{-1} = e^{phi(n)-1} (mod phi(n))
>
>since phi(n) = 0 (mod phi(n))
You are on the right track, but missing a phi:
e^{-1} = e^{phi(phi(n)) - 1} (mod phi(n))
by Euler's theorem.
>The result is a quite huge number, but you can use modulo reduction after
>every multiplication:
Observer that your code is no faster than searching for an inverse.
If you had used square and multiply to exponentiate, this would
have been faster.
--
Kristian Gjųsteen
Timo Johansson
> Timo Johansson <joha...@despammed.com> wrote:
>>TJakobsen wrote:
>>>d is calculated like this:
>>>
>>> d = e^-1 (mod phi(n))
>>
>>d = e^{-1} = e^{phi(n)-1} (mod phi(n))
>>
>>since phi(n) = 0 (mod phi(n))
>
> You are on the right track, but missing a phi:
>
> e^{-1} = e^{phi(phi(n)) - 1} (mod phi(n))
>
> by Euler's theorem.
yes of course...!!!
>>The result is a quite huge number, but you can use modulo reduction after
>>every multiplication:
>
> Observer that your code is no faster than searching for an inverse.
> If you had used square and multiply to exponentiate, this would
> have been faster.
>
You're absolutely right. For the beginning I just wanted to give the most
simple solution I could imagine. Although, SQ+MUL is very easy to
implement, TJakobsen: See the "handbook of applied crypto".