Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 25 of 25

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

  1. #1
    Java kindergarten chronoz13's Avatar
    Join Date
    Mar 2009
    Location
    Philippines
    Posts
    659
    Thanks
    177
    Thanked 30 Times in 28 Posts

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

    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) ?
    Last edited by chronoz13; September 21st, 2011 at 07:04 PM.


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default 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

  3. #3
    Java kindergarten chronoz13's Avatar
    Join Date
    Mar 2009
    Location
    Philippines
    Posts
    659
    Thanks
    177
    Thanked 30 Times in 28 Posts

    Default 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

  4. #4
    Java kindergarten chronoz13's Avatar
    Join Date
    Mar 2009
    Location
    Philippines
    Posts
    659
    Thanks
    177
    Thanked 30 Times in 28 Posts

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

  5. #5
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

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

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

  6. #6
    Java kindergarten chronoz13's Avatar
    Join Date
    Mar 2009
    Location
    Philippines
    Posts
    659
    Thanks
    177
    Thanked 30 Times in 28 Posts

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

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

  7. #7
    Java kindergarten chronoz13's Avatar
    Join Date
    Mar 2009
    Location
    Philippines
    Posts
    659
    Thanks
    177
    Thanked 30 Times in 28 Posts

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

    the formula to encrypt a message is
    m raise to e mod pq
    where <m> is the original message(character)

    the formula to decipher is
    c raise to e mod pq
    where <c> is the encrypted message(character)

    i followed these steps.. im really stuck up

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

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

  9. #9
    Java kindergarten chronoz13's Avatar
    Join Date
    Mar 2009
    Location
    Philippines
    Posts
    659
    Thanks
    177
    Thanked 30 Times in 28 Posts

    Default 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
    so basically, theres no easy way for this one? .. , i just really want to know how to make the equation right...

  10. #10
    Java kindergarten chronoz13's Avatar
    Join Date
    Mar 2009
    Location
    Philippines
    Posts
    659
    Thanks
    177
    Thanked 30 Times in 28 Posts

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

    1823 mod 55 = 181 *182 * 184 * 1816 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 1823 mod 55

  11. #11
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

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

    So the website is wrong.

  12. #12
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

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

  13. #13
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

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

  14. #14
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

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

    Very good Sean. Using BigDecimal does it.

  15. #15
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

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

    Using BigDecimal does it.
    There's one slightly even better choice for large integers!

  16. #16
    Java kindergarten chronoz13's Avatar
    Join Date
    Mar 2009
    Location
    Philippines
    Posts
    659
    Thanks
    177
    Thanked 30 Times in 28 Posts

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

    18*49*36*26
    yes , now i notice this part and how does the 18 raise to 23 was divided into 4 parts
    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?
    Last edited by chronoz13; September 22nd, 2011 at 07:43 AM.

  17. #17
    Java kindergarten chronoz13's Avatar
    Join Date
    Mar 2009
    Location
    Philippines
    Posts
    659
    Thanks
    177
    Thanked 30 Times in 28 Posts

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

  18. #18
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

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

    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));
      }
    }
    Last edited by Sean4u; September 22nd, 2011 at 07:53 AM.

  19. #19
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

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

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

  20. #20
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

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

    Now we're getting into higher math.

  21. #21
    Java kindergarten chronoz13's Avatar
    Join Date
    Mar 2009
    Location
    Philippines
    Posts
    659
    Thanks
    177
    Thanked 30 Times in 28 Posts

    Default 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
    18^1 *18^2 * 18^4 * 18^16 / a^(b+c) = a^b * a^c
    , just excuse my slowness with some equations,

  22. #22
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

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

    1+2+4+16 = 23

  23. #23
    Java kindergarten chronoz13's Avatar
    Join Date
    Mar 2009
    Location
    Philippines
    Posts
    659
    Thanks
    177
    Thanked 30 Times in 28 Posts

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

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

  24. #24
    Super Moderator Sean4u's Avatar
    Join Date
    Jul 2011
    Location
    Tavistock, UK
    Posts
    637
    Thanks
    5
    Thanked 103 Times in 93 Posts

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

  25. The Following User Says Thank You to Sean4u For This Useful Post:

    chronoz13 (September 22nd, 2011)

  26. #25
    Java kindergarten chronoz13's Avatar
    Join Date
    Mar 2009
    Location
    Philippines
    Posts
    659
    Thanks
    177
    Thanked 30 Times in 28 Posts

    Default 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

Similar Threads

  1. Please help me to find a sample application devloped using Java 1.7
    By kondapalli_kumar in forum Java Theory & Questions
    Replies: 1
    Last Post: September 9th, 2011, 10:12 AM
  2. I need help (Sample code)
    By AGBESI in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 2nd, 2011, 06:10 AM
  3. java xml parsing sample
    By HungryCoder in forum Java SE APIs
    Replies: 1
    Last Post: May 25th, 2011, 10:48 AM
  4. Alice in Javaland
    By Alice in forum Member Introductions
    Replies: 4
    Last Post: December 3rd, 2010, 10:45 PM
  5. free scjp 1.6 sample questions
    By sumanjava11 in forum The Cafe
    Replies: 1
    Last Post: August 19th, 2009, 04:00 AM