Results 1 to 5 of 5

Math Help - RSA encryption and decryption

  1. #1
    Newbie
    Joined
    Aug 2013
    From
    hcm
    Posts
    19

    RSA encryption and decryption

    Hi everyone, I don't know how to decrypt and encrypt ciphertext using RSA cryptosystem.
    I have a problem:
    Let n=4189, e=3, d=2707. Encrypt DO(0314) and decrypt 3971.

    I think to encrypt DO (0314)
    0314^3 mod 4189 = 2434
    but I don't know how to decrypt 3971
    3971^2707 mod 4189 =?

    Please help me. Thank you very much.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: RSA encryption and decryption

    Hey math88.

    Hint: Use the result a^(b+c) mod n = (a^b mod n)*(a^c mod n) mod n and break things into powers of 2.

    The highest power of 2 is 2048 for 2707. Then you can use this to find your answer.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2013
    From
    hcm
    Posts
    19

    Re: RSA encryption and decryption

    Could you be more specific? I don't understand why we need the highest power of 2.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    539
    Thanks
    218

    Re: RSA encryption and decryption

    Hi,
    The decrypted value is 614. I did not do this by hand; certainly the RSA algorithm is not meant to be done by hand. What is needed once e, d and n are specified is a way to compute xm mod n (encryption m=e and decryption m=d).

    Here is C code to do exactly this. The first is recursive and the second is non-recursive. With enough patience you can do these algorithms by hand to arrive at 614, but I'm too lazy.

    Code:
    /* Recursive computation of x^m mod n (so n != 0) where m>0.
    Of course ints involved must be all < MAX_INT and also n^2 < MAX_INT
    Algorithm works because x^m=(x^(m/2))^2*x^(m%2).  At each step the result
    is reduced mod n.
    */
    int powmod(int x,int m,int n) {
    	int temp;
    	if (m==1) {
    		return(x%n);
    	}
    	temp=powmod(x,m/2,n);
    	temp*=temp;
    	if (m&1==1) {
    		temp%=n;
    		temp*=x;
    	}
    	return(temp%n);
    }
    /* Computes x^m mod n as in recursivePowmod.  Same caveats as there.  The validity
       of this technique can be verified by considering m written in binary.  This is more
       efficient than the above because it takes away the log(m) function calls, but practically
       there is little difference in efficiency.
    */
    int powmod1(int x,int m,int n) {
    	int z=1,y=x;
    	while (m>0) {
    		if (m&1==1) {
    			z=z*y%n;
    		}
    		y=y*y%n;
    		m>>=1;
    	}
    	return(z);
    }
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: RSA encryption and decryption

    As an example lets say you want to calculate 3^129. In binary this is 129 = 128*1 + 1*1. So you have to calculate 2^129 = 2^128*2^1.

    You calculate 3^1 mod n, 3^2 mod n, 3^4 mod m, 3^16 mod n 3^32 mod n, ..., 3^128 mod n. You do this by squaring the previous value and simplifying mod n.

    Then you use the fact that a^(b+c) = a^b * a^c and use the results to obtain mod n.

    The reason you use binary is because you can use x = a*2^n + b*2^(n-1) + ... + z where the coefficients are either 0 or 1.

    Another example is say 72 = 1*64 + 0*32 + 0*16 + 1*8 + 0*4 + 0*2 + 0*1 or 75 = 1*64 + 0*32 + 0*16 + 1*8 + 0*4 + 1*2 + 1*1.

    By using the results of a^(2n) you can use these in addition to a^(b+c) = a^b * a^c to figure out really large values (if you don't have a computer).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. RSA Decryption method
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: November 7th 2011, 04:11 PM
  2. Hill 2-Cipher Decryption
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: September 28th 2010, 01:45 PM
  3. RSA and number of decryption exponents
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 17th 2010, 11:24 AM
  4. show encryption and decryption are identical
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: April 29th 2008, 03:43 AM

Search Tags


/mathhelpforum @mathhelpforum