0
$\begingroup$

So I have the value of N. I have to use this value of N to find the value of D.

N = 265291078722948385089717069136983657793

Now I read about RSA algos and found out that

N=PQ | where P and Q are prime factors 

I found -
P - 14716976826788780483
Q - 18026193955816294571

  1. The following is an example of what I've approached

    Choose p = 3 and q = 11
    Compute n = p * q = 3 * 11 = 33
    Compute φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20
    Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 7
    Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 3 [(3 * 7) % 20 = 1]

  2. We have

    P = 14716976826788780483
    Q = 18026193955816294571
    N = 265291078722948385089717069136983657793
    E = 65537 (given)
    φ(n) = 265291078722948385056973898354378582740 [using (p-1)(q-1)]

I'm unable to solve the equation (d * e) % φ(n) = 1 for the above values. We need to find/derive D.

I tried using this online calculator Princeton Extended Calc But it doesn't accept large values

Any help is appreciated

Improve this question
$\endgroup$
1
$\begingroup$

Wolfram alpha can do this:

http://www.wolframalpha.com/input/?i=multiplicative+inverse+of+65537+mod+265291078722948385056973898354378582740

yields

d = 240894030773496778838526583320400223673

The alternative is to write a small C program using gmp or using python, e.g.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ More than answer the question giving the number, I feel it would be better to explain the process and how to find the result. This would be useful for all other people having a similar problem with a different number. $\endgroup$ – ddddavidee Nov 16 '15 at 20:19
  • 1
    $\begingroup$ The OP used an online calculator so I referred him to another one that does work $\endgroup$ – Henno Brandsma Nov 16 '15 at 20:21
  • 1
    $\begingroup$ "Give a man a fish and you feed him for a day; teach a man to fish and you feed him for a lifetime." Generally, for homework questions like this pointers towards the correct way are much more useful than just handing over the result. $\endgroup$ – tylo Nov 17 '15 at 13:30
0
$\begingroup$

Seeing code might help you, it should be this if I remember correctly. For large numbers you should use an NTL library.

/* 
   Recursive version of the euclidean algorithm, because it's much faster.
*/
void extendedEuclid(long a, long b, long& x, long& y)
{
        if (a%b== 0)
        {
            x = 0;
            y = 1;
            return;
        }
        extendedEuclid(b,(a%b), x, y);
        long temp = x;
        x = y;
        y = temp - (y*(a//b));
}
/*
    Mudular inverse of a x = 1 mod m;
    returns x in this case.
*/
long modInverse(long a, long d)
{
    long x, y;
    extendedEuclid(a, d, x, y);
    if (!(x > zero()) && !(x ==0)) 
      x =(x+d);
    return x;
}
Improve this answer
$\endgroup$
  • 1
    $\begingroup$ long is also not big enough. Use gmp or some other bignum library, if you want C. Of course Python will do this OK, as it has bignums built in. $\endgroup$ – Henno Brandsma Dec 17 '15 at 21:36
0
$\begingroup$

If you want to try with some Python code:

   def egcd(a, b):
        if a == 0:
            return (b, 0, 1)
        else:
            g, y, x = egcd(b % a, a)
            return (g, x - (b // a) * y, y)


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.