Win a copy of Spring in Action (5th edition) this week in the Spring forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • paul wheaton
Saloon Keepers:
  • Ganesh Patekar
  • Frits Walraven
  • Tim Moores
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Stephan van Hulst
  • salvin francis
  • Tim Holloway

RSA algorithm(java)  RSS feed

 
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
package rsa;

/**
*
* @author Palllvi T M
*/
import java.util.Scanner;

public class Rsa {
   public static int mult (int x,int y,int n){
       int k=1;
       int j;
       for(j=1;j<=y;j++);
       k=(k=x)%n;
       return k;
   }
public static int gcd(int m,int n){
   if (n==0)
       return m;
   else
       return (gcd(n,m%n));  
}
    /**
    * @param args the command line arguments
    */
   public static void main(String[] args) {
       // TODO code application logic here
int msg, PlainText,CipherText;
int n,d=0,e,z,p,q,i;
Scanner sc=new Scanner(System.in);
System.out.print("enter the values of primes p and q");
p=sc.nextInt();
q=sc.nextInt();
System.out.print("enter msg such that(msg is less than or equal to(p*q)-z");
msg=sc.nextInt();
n=p*q;
z=(p-1)*(q-1);
do{
   System.out.print("choose the value of e(e>z) such that gcd(z,e)=1:");
   e=sc.nextInt();
}while(gcd(z,e)!=1);
       i=2;
       while(((i*e)%z)!=1)
       {
   i++;
   d=i;
}
System.out.println("the public key pair is("+e+","+n+")");
System.out.println("the public key pair is("+d+","+n+")");
CipherText=mult(msg,e,n);
System.out.println("CipherText="+CipherText);
PlainText=mult(CipherText,d,n);
System.out.println("PlainText="+PlainText);

}
   }
   



output:
enter the values of primes p and q5 7
enter msg such that(msg is less than or equal to(p*q)-z30
choose the value of e(e>z) such that gcd(z,e)=1:5
the public key pair is(5,35)
the public key pair is(5,35)
CipherText=30
PlainText=30

is the output correct???
if not please tell me the changes
 
Ranch Hand
Posts: 106
5
MS IE Notepad Suse
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I didn't tried to read your stuff as
1) it doesn't use code tags
2) uses 32-bit ints
3) input is wrong as you re-use one of the primes

Wikipedia uses these values:

p = 61
q = 53

This gives N = p x q = 61 x 53 = 3233

EN.wiki uses Carmichael's totient function - I don't know this and instead use what Java uses and what is used on DE.wiki: Euler's totient function - wich is: phi(N) = (p-1) x (q-1) = (61 - 1) x (53 - 1) = 60 x 52 = 3120

Now you have to choose e - wich has to be co-prime to phi(N) - this where you made your mistake and re-used p - NO! - you have to use something else! In real security a common used value is 65537 - wich is 2^16+1 - 4th Fermat number. Wiki choosen e = 17.

So, public key is (N,e) = (3233,17)

Now, you have to calculate d - and this is where standard API comes in - java.math.BigInteger offers the method modInverse() wich is also used in SUNs RSA implementation - wich in this case gives you d = 413.

So, private key is (N,d) = (3233,413)

Then the RSA-"magic" is : m^e mod N - where m is the message - your code shows two errors:

for(j=1;j<=y;j++); <br /> <br /> Dang - loop without body. <br /> <br /> k=(k=x)%n; <br /> <br /> I doubt this is valid java code. Also, whatever this is meant to do - it's not what you think. Again, this is where standard API offers (and is used) : BigInteger.modPow(). <br /> <br /> To sum it up: <br /> <br /> <br /> According to grepcode - this is real java code: <br /> <br /> <br /> So, it's easy to spot that something is wrong with what you tried, as 30^5 mode 35 cleary isn't 30 - but 25. <br /> <br /> Advice: don't try to write your own security - use what Java already provides and what's common: create random AES key - wrap with RSA and use AES for message encryption - this looks - warning: bad code incoming - something like this: <br /> <br /> <br />


But what you really should use is TLS. Hint: for generating certificate either use OpenSSL if you have access to linux - otherwise you can get a PKI up with bouncycastle. But that's a topic for another thread.
 
Marshal
Posts: 61754
193
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Pallavi Tumbigeremat wrote:.  . .
       for(j=1;j<=y;j++);
       k=(k=x)%n;
. . .

Code tags or no code tags, please explain those two lines.

Too difficult a question for its current location: moving to our security forum.
 
Matt Wong
Ranch Hand
Posts: 106
5
MS IE Notepad Suse
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
so - first of all - I cleaned up your code - re-formatted it - and, most important of all - put it into code-tags:


so - now lets try to split up what you tried - what you did - and what went wrong

Line 33/34

yes - it's "legal" java code - but - conventions states, that each variable is written in its own line - so it should look like this:

next logic issue: primitives always set to thier defaults - for int default is 0 - but - it makes a difference if you just declare a reference - or if you correctly initialize it
also - convention: variables use "lowerCamelCase"
to pretty it up - that's what it should look like:


next we got at line 36 - Scanner-mess

Ok - you got it working - but I guess only by luck - you shouldn't try to read console input this way.
Here you have a more reliable one:

So here is something a bit more common - so it's also way better recognized by experienced coders:


I'm not quite sure about that "less than (p*q)-z" - but "equal to" is surely wrong as this would result in "0" - so it has to be "less than". Also - you're using Euler PHI function - so your "z" should named "phi" or "phiN":

Just look at my code - or at SUNs code.

So you say your message should be "less than or equal" than: p x q - phiN
No parentheses need as basic math rule states: "multiply/divide always comes before addition/subtraction" - so writing "p x q - phiN" implies you also do "p x q" first - wich is N - and then do "N - phiN" as second step.
Also we now see - this is wrong. In RSA message has to be one bit shorter than modulus: for RSA2048 with N.length 2048 message can up to 2047 bits - as we use 8 bit per byte in modern computers - next lowest value would be 2040bits - this is clearly bigger than "N - phiN". Remember: phiN is (p-1) x (q-1), so you would end up with limit of:

p x q - (p-1)x(q-1)

Simple not-so-real-world-example with some big primes:

p=63709
q=48487

We ignore that it should be: p < q - for this example. <br /> <br /> N=3089058283 <br /> phiN=(63709-1)x(48487-1)=63708x48486=3088946088 <br /> <br /> So with your limit you would end up with just 112195 - wich is just 17 bits - but you could go up to 31 bits - wich would be 2147483647 - when bound to 8bit-per-byte - we would end up with 24bits wich would be 16777215. <br /> <br /> Next: line 48 <br />
Ok - text says what you try to get here - a random number co-prime to phiN. At least you're doin the right thing wich I didn't - you checked for co-prime.
Why is co-prime important? If you get a non-co-prime you end up with a multiple of phiN wich ends up in "0" after modulus.

Line 54

Not sure about that - about it looks like modInverse to calculate d. This is already in Java: BigInteger.modInverse().

Last line: 9

I didn't even tried to understand what you tried to do here - but "for();" is just an empty loop after wich you do nothin with your counter so you end up with just return x%n - wich obviously isn't the RSA "magic" function: msg^e mod N.


So, after going through your code one can easy spot some issues wich clearly breaks what ever you tried to accomplish.
This is why you should not try to implement your own crypto - and as you seen - I missed check for co-prime - so even I'm really into this stuff - I also made a huge mistake wich could end up in just "0" by getting unlucky with primes. Even the bit I posted below wich at least tries to go for somewhat like anonymous RSA with AES - it's garbage and shouldn't used even for local file encryption.

If you want I could go for way more secure way using BouncyCastle wich provides secure ways to generate and handle local file encryption. For network connections you should go with TLS - wich Java always brings along and needed certificates can easy generated with openssl or with BouncyCastle.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!