multiplicative inverse finding algorithm

I am trying to implement RSA for my FPGA.



And there is a inverse modulo operation that is bugging me for 3 days now, problem is--

(551)^-1 mod 1517 = 1082 !!

i dont know how, but this is the result.

taken from--
"An efficient Montgomery exponentiation Algorithm for cryptographic applications"--p 462
http://www.mii.lt/Informatica/pdf/INFO600.pdf (152 KB)

first, i cant understand how he got that result, second i cant find a algorithm for multiplicative
inverse with modular operation. and So, i am in big big trouble.


In the following pdf, there is a efficient solution for inverse--

"Bit serial Systolic architectures for multiplicative inversion and division" (p -51)
http://etd.uwaterloo.ca/etd/akdanesh2005.pdf (879 KB)

since, i dont know how

(551)^-1 mod 1517 = 1082 !!

was computed, i couldn't figure out how to debug and what to expect.

please please help if possible.

to say that b is the modular inverse mod m of a is to say that

a * b = 1 (mod m)

for any integer a, there exist such an inverse b if and only if a and b are relatively prime. Using the extended euclidean algorithm we can find an x and y such that a * x + m * y = 1. From that is is apparent that a * x = 1 (mod m), therefore x is the modular inverse of a.

Salams

how are you guys

im just trying to implement the same RSA in assembly language(So if someone can help please dont hesitate!!)...

this inverse modulo is the hardest part..it needs an extended euclidean method ...and alot of complexity....

but the idea is that....whenever you multiply a number (a) with its inverse modulo (b)...and devide the result with ( m) ... you should get the remainder 1 ...
....
thats all !

the problem is how to implement it :S ...and with fpga its more complicated :S....
.........

salams

Suppose that you are trying to calculate the modular inverse of px (mod py). You would do it in the following way (written in c++)

Code:

---

        int x = px;
        int y = py;
       
        //Setup initial variables
        //Maintain throughout that ax * px + bx * py = x and that ay * px + by * py = y
        int ax = 1;
        int ay = 0;
        int bx = 0;
        int by = 1;
       
        //Perform extended gcd
        while(x)
        {
                if(x <= y)
                {
                        int m = y / x;
                        y -= m * x;
                        ay -= ax * m;
                        by -= bx * m;
                }
                else
                {
                        swap(x, y);
                        swap(ax, ay);
                        swap(bx, by);
                }
        }
       
        //you can assert that ay * px + by * py = y = gcd(px, py)
        //you can assert that ax * px + bx * py = x = 0
       
        //If we're taking the modular inverse of px (mod py), then for it to exist gcd(px, py) = 1
        //If it does exist, it is given by ay (mod py)
        int inverse = ay % py;
        if(inverse < 0) inverse += py;

---

hey ,
can someone pliz help me with the project m doin..
i want to implement rsa crypto system in c++
but m finding it difficult to calculate d since i dont know how to code the part where we find inverse of e..

pliz i urgently need sm1 help..

ax + by = d(GCD)
x = a ^ -1 % b
y = b ^ -1 % a

D is GCD for a and b.

Am i correct ?

Thanks.

Quote:

---

Originally Posted by security

hey ,
can someone pliz help me with the project m doin..
i want to implement rsa crypto system in c++
but m finding it difficult to calculate d since i dont know how to code the part where we find inverse of e..

pliz i urgently need sm1 help..

---

here is toy-RSA ... for 32-bit prime integers....but in C

Code:

---

#include<stdio.h>
#include<string.h>

struct keys
{
    unsigned long int n;
    unsigned long int de;
};

int lenp,lend;

int testprime(int no)
{
    int i;
    for(i=2;i<no;i++)
    {
        if((no &#37; i) == 0)
        {
            return 0;           
        }
    }
    return 1;
}

int testgcd(int dividend,int divisor)
{
    int rem=-1;
    while(rem != 0)
    {
        rem=dividend % divisor;
        dividend=divisor;
        if(rem != 0)
          divisor=rem;
    }
    return divisor;
}

unsigned long int expocal(unsigned long int c,unsigned long int d,unsigned long int n)
{
    unsigned long int i=0,ans=1;
    for(i=1;i<=d;i++)
    {
      ans=ans%n;
      ans=ans*c;
    }
    ans=ans%n;
    return ans;   
}

unsigned long int findd(unsigned long int e,unsigned long int phi)
{
    unsigned long int d=1,rem=-1,test;
    while(rem!=0)
    {
        test=e*d;
        test=test-1;
        rem=test%phi;
        if(rem==0)
            return d;
        d++;
    }
    return 0;
}

unsigned long int rsa_encryption(struct keys publickey,unsigned int long m)
{
    return expocal(m,publickey.de,publickey.n);
}

unsigned long int rsa_decryption(struct keys privatekey,unsigned long int c)
{
    return expocal(c,privatekey.de,privatekey.n);
}

void padding(char *p)
{
    int i;
    for(i=0;i<lenp;i++)
    {
        p++;
    }
    for(i=lenp;i<lend;i++)
    {
        *p=(int) NULL;
        p++;
    }
}

void rsa_algorithm(unsigned long int p,unsigned long int q,int pt)
{
    struct keys publickey,privatekey;
    unsigned long int n,phi,e,d,ct;
    register int i=0;
    n=p*q;
    phi=(p-1)*(q-1);   
    for(i=2;i<phi;i++)
    {
        if(testgcd(phi,i)==1)
        {
            printf("\t| %lu |\t",i);
        }
    }
    printf("\n\nSelect a value of e from the above list\n");
    scanf("%lu",&e);
    while(testgcd(phi,e)!=1)
    {
        printf("uncompatible value of e. choose another value for e\n");
        scanf("%lu",&e);
    }
    publickey.n=n;
    publickey.de=e;
    privatekey.n=n;
    d=findd(e,phi);
    printf("d=%lu\n",d);
    privatekey.de=d;
    ct=rsa_encryption(publickey,pt);
    printf("ct=%d\n",ct);
    pt=rsa_decryption(privatekey,ct);
    printf("pt=%d\n",pt); 
}   

int main()
{
    unsigned long int pr1,pr2,pt;
    printf("Enter an integer(plain-text value)");
    scanf("%lu",&pt);
    printf("enter 2 prime numbers");
    scanf("%lu,%lu",&pr1,&pr2);
    while(testprime(pr1)==0)
    {
        printf("the number %lu is not prime\nenter a prime no",pr1);
        scanf("%lu",&pr1);
    }
    while(testprime(pr2)==0)
    {
        printf("the number %lu is not prime\nenter a prime no",pr2);
        scanf("%lu",&pr2);
    }
    rsa_algorithm(pr1,pr2,pt);
    return 0;
}

---

Another way to compute the modular inverse of a number is by using Euler's totient function. This is a bit easier to understand but harder to implement in computers.

The Euler's totient function (Phi) of a number n is the total numbers smaller than n that are coprime to n. From this, the formula to compute the modular inverse is:

a^-1 = a^(Phi(m) -1) (mod m)

In your case you have 551^-1 mod 1517.

First we find the prime factors of 1517, which are 37 and 41. Then we use the formula for Phi (see it here: http://en.wikipedia.org/wiki/Euler's_totient_function).

Phi(1517) = 1517 * (1 - (1/37)) * (1 - (1/41)) = 1440.

Then a^(Phi(m) -1) = 551^1439

In windows calculator compute (551^1439) mod 1517 and the answer is 1082.

As you can see this involved the factorization of 1517 and this is considered a hard problem for computers. However, computing the Euler's totient function of a prime number is trivial. If n is prime then Phi(n) = n-1, since all the numbers from 1 to n-1 would be coprime to n.

Most encryption algorithms require choosing prime numbers (the larger the better) so using this approach the computation of the modular inverse would be a constant complexity operation, i.e an easy problem for a computer.