CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8
  1. #1
    Join Date
    Jan 2008
    Posts
    3

    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.

  2. #2
    Join Date
    Apr 2005
    Location
    Livonia Michigan
    Posts
    142

    Re: multiplicative inverse finding algorithm

    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.
    The Strawdog's out in the street

  3. #3
    Join Date
    Jan 2008
    Posts
    1

    Re: multiplicative inverse finding algorithm

    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

  4. #4
    Join Date
    Apr 2005
    Location
    Livonia Michigan
    Posts
    142

    Re: multiplicative inverse finding algorithm

    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;
    Last edited by msg555; January 16th, 2008 at 04:00 PM.
    The Strawdog's out in the street

  5. #5
    Join Date
    Oct 2008
    Posts
    1

    Re: calculatin inverse for e in rsa

    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..

  6. #6
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    Re: multiplicative inverse finding algorithm

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

    D is GCD for a and b.

    Am i correct ?

    Thanks.
    Thanks for your help.

  7. #7
    Join Date
    Oct 2007
    Posts
    63

    Re: calculatin inverse for e in rsa

    Quote Originally Posted by security View Post
    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;
    }

  8. #8
    Join Date
    Nov 2010
    Posts
    1

    Re: multiplicative inverse finding algorithm

    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured