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) ?

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

let me edit my post, im sorry i put single quotation on 2

i just dont get it right.. im following the formula , but i ended up in a confusing value.

That's the way it goes sometimes.
Double check your code.

i did everthing i could .. i really dont get the math :(

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 :(

You'll have to find a math guy for help on this one.

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

Quote:

---

18²³ mod 55 = 18¹ *18² * 18⁴ * 18¹⁶ 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²³ mod 55

So the website is wrong.

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

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

Very good Sean. Using BigDecimal does it.

Quote:

---

Using BigDecimal does it.

---

There's one slightly even better choice for large integers!

Quote:

---

18*49*36*26

---

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?

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?

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));
  }
}

---

a^(b+c) = a^b * a^c

Now we're getting into higher math.

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,

1+2+4+16 = 23

Quote:

---

1+2+4+16 = 23

---

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

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.

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