
RSA encryption based from a Sample Alice and Bob's key.
i followed the step by step procedure how to encrypt and decipher a message based on a basic RSA encryption/deciphering steps from this article The RSA public key cryptographic system (in Technology > Encryption @ iusmentis.com)
Code :
public class RSA {
public static void main(String[] args) {
int p = 5,
q = 11,
e = 7,
d = 23;
int encrypted = encrypt(2, e, p, q);
System.out.println("Encrypted :" + encrypted);
int deciphered = decipher(encrypted, d, p, q);
System.out.println("Deciphered" + deciphered);
}
public static int encrypt(int sampleChar, int e, int p, int q) {
return (int) (Math.pow(sampleChar, e) % (p * q));
}
public static int decipher(int encryptedSampleChar, int d, int p, int q) {
return (int) (Math.pow(encryptedSampleChar, d) % (p * q));
}
}
an original message which is 2 is encrypted by [2 raise to e modulo of (p * q)] resulting into 18
but in the state of deciphering by [18 raise to d modulo of (p * q)] results into 37, instead of 2
i directly assigned 23 as the value of d, to lessen some code because its already given on the article sample
i just dont get it right, why do i get 37 instead of 2 when i try to revert the process (deciphering) ?

Re: RSA encryption based from a Sample Alice and Bob's key.
int encrypted = encrypt(2, e, p, q); // here value is 2
vs
int encrypted = encrypt('2', e, p, q); // here it is '2' or 50

Re: RSA encryption based from a Sample Alice and Bob's key.
let me edit my post, im sorry i put single quotation on 2

Re: RSA encryption based from a Sample Alice and Bob's key.
i just dont get it right.. im following the formula , but i ended up in a confusing value.

Re: RSA encryption based from a Sample Alice and Bob's key.
That's the way it goes sometimes.
Double check your code.

Re: RSA encryption based from a Sample Alice and Bob's key.
i did everthing i could .. i really dont get the math :(

Re: RSA encryption based from a Sample Alice and Bob's key.
the formula to encrypt a message is
Quote:
m raise to e mod pq
where <m> is the original message(character)
the formula to decipher is
Quote:
c raise to e mod pq
where <c> is the encrypted message(character)
i followed these steps.. im really stuck up :(

Re: RSA encryption based from a Sample Alice and Bob's key.
You'll have to find a math guy for help on this one.

Re: RSA encryption based from a Sample Alice and Bob's key.
Quote:
You'll have to find a math guy for help on this one
so basically, theres no easy way for this one? .. :( , i just really want to know how to make the equation right...

Re: RSA encryption based from a Sample Alice and Bob's key.
Quote:
18^{23} mod 55 = 18^{1} *18^{2} * 18^{4} * 18^{16} mod 55 = 18*49*36*26 mod 55 = 825552 = 15010*55 + 2 = 2 mod 55.
i followed this formula but i get the value 37 instead of 2, from 18^{23} mod 55

Re: RSA encryption based from a Sample Alice and Bob's key.

Re: RSA encryption based from a Sample Alice and Bob's key.
I read your link and it seems the person who wrote it may not have been paying attention during the last example:
Quote:
1823 mod 55 = 18^1 *18^2 * 18^4 * 18^16 mod 55 = 18*49*36*26 mod 55 = 825552
Does that look right to you?
How does your code work if you use the values in the WP article?
RSA  Wikipedia, the free encyclopedia
edit: D'oh! Too slow again

Re: RSA encryption based from a Sample Alice and Bob's key.
Something that you might want to bear in mind is that you might be using quite large numbers and a technique that depends on integer values with Math.pow(). You might get lucky as long as your numbers are very small, but still...

Re: RSA encryption based from a Sample Alice and Bob's key.
Very good Sean. Using BigDecimal does it.

Re: RSA encryption based from a Sample Alice and Bob's key.
Quote:
Using BigDecimal does it.
There's one slightly even better choice for large integers!

Re: RSA encryption based from a Sample Alice and Bob's key.
yes , now i notice this part and how does the 18 raise to 23 was divided into 4 parts
Quote:
18^1 *18^2 * 18^4 * 18^16
or how does the exponent 23, was divided into 4 parts... and i was also thinking that I MIGHT be calculating the number so large that it generates a "inexact" value?

Re: RSA encryption based from a Sample Alice and Bob's key.
while im reading the WP article, i think i should ask this to have a bottom point for the problem. i somehow resolve my issue by using the
Quote:
18^1 *18^2 * 18^4 * 18^16 % 55
explicitly, my question will be, what is the logic of how does the (d exponent) in this case 23, divided into 4 parts?

Re: RSA encryption based from a Sample Alice and Bob's key.
That part is right, it's the next bit that's completely wrong. I only looked at it because I wondered if you were getting integer overflow. 18 is a bit more than 2^4. a^b^c is a^b*c, so 2^92 (4 times 23) ish will blow an int away completely  and probably a double too.
Code java:
package com.javaprogrammingforums.domyhomework;
public class RSAIntBad
{
public static void main(String[] args)
{
for (int i = 0; i <= 23; i++)
System.out.println("18^" + i + " is " + (int)Math.pow(18, i) + " should be " + new java.math.BigInteger("18").pow(i));
}
}

Re: RSA encryption based from a Sample Alice and Bob's key.

Re: RSA encryption based from a Sample Alice and Bob's key.
Now we're getting into higher math.

Re: RSA encryption based from a Sample Alice and Bob's key.
well yeah, i have 2 ways to deal with the problem, studying the use of the BigDecimal/BigInteger, and trying to logicaly understand
Quote:
18^1 *18^2 * 18^4 * 18^16 / a^(b+c) = a^b * a^c
, just excuse my slowness with some equations,

Re: RSA encryption based from a Sample Alice and Bob's key.

Re: RSA encryption based from a Sample Alice and Bob's key.
yes i do get that one, but my concern is, how am i going to divide into parts and how many parts if my exponent is , for example , 30 or 17 or 40 or 28 etc..

Re: RSA encryption based from a Sample Alice and Bob's key.
The maths is quite useless to you as a programmer. I keep meaning to write a Number class that is based on factorisation (so it never actually does any maths, just remembers lists of factors until you explicitly ask for a typed result) which would take advantage of this sort of thing, but it would be an intellectual curiosity.
<phone rings>you got the job, pending references checking out</phone rings>Woohoo! Rain in the desert! I'm not wet yet, but I am ready to drink!
Back to the plot. The only reason it's interesting right now is that the author of that page seems to have mangled his maths and somehow came up with the answer that was required to make the example work, when as you have observed, it does not.
I'm not sure how BigInteger works internally, but it does avoid any issues with breaking down the problem into more manageable pieces by always guaranteeing to be 'big enough'. You're only looking at a toy example at the moment, but from looking at what RSA does, you'll be computing some meaninglessly large numbers when you use that code in anger. int and double, even though 4 billion and [whatever it is that double offers] sound large, are pitifully small in comparison.

Re: RSA encryption based from a Sample Alice and Bob's key.
maybe i should end the discussion here, i just noticed that this will be a bottomless pit, out of the curiosity that became an obssesion that i got from that basic RSA, and i never thought that there are classes like BigIntegers/BigDecimal that solves an impractical approach to simple integer calculations, thanks again