Results 1 to 4 of 4

Math Help - Encoding Problem & Algorithm

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    14

    Encoding Problem & Algorithm

    This problem is about the RSA cryptosystem; a process by which people can
    communicate securely. It is widely used in today’s society.
    It is possible to turn every English phrase into a sequence of numbers. Assign the letters of the
    alphabet A,B,C,. . .,Y,Z with the numbers 0, 1, 2, . . . , 24, 25, respectively.
    We’ll deal with 2 letters at a time: every pair of letters can be uniquely represented by a number
    less than 676 in base 26 notation. Every pair of letters corresponds to some between 0 and 675
    inclusive, and any such number corresponds to a pair of letters.
    For example, to convert DISCRETE into numbers we would do the following: DI–SC–RE–TE
    becomes
    D is 3, I is 8: so DI is 3 × 26 + 8 = 80.
    S is 18, C is 2: so SC is 18 × 26 + 2 = 470.
    R is 17, E is 4: so RE is 17 × 26 + 4 = 446.
    T is 19, E is 4: so TE is 19 × 26 + 4 = 498.
    Thus, DISCRETE would be written 80–470–446–498.
    Conversely, if we are given a sequence of numbers less than 676, then we can convert them into
    English by using the division algorithm with divisor 26. To translate 352–501–13–278 we find
    352 = 13 × 26 + 14
    501 = 19 × 26 + 7
    13 = 0 × 26 + 13
    278 = 10 × 26 + 18;
    and so we’d get letters 13,14,19,7,0,13,10,18; which reads NOTHANKS.
    A simplistic version of the RSA cryptosystem works in the following way: select two primes p and
    q so that pq is just bigger than 676. The best available choice is p = 7, q = 97, so that pq = 679.
    Now choose any integer e > 1 which is relatively prime to (p − 1)(q − 1). It turns out we just need
    to choose any integer e > 1 not divisible by 2 or 3.
    To encrypt a message M, first turn it into a sequence of integers M1,M2, . . . ,Mk, all less than 676.
    Now calculate Ci = Mei mod pq for each i. Your calculations will give you k numbers C1,C2, . . . ,Ck
    all less than pq = 679. Convert this sequence back to English to get your encrypted message. (If you get 676,677 or 678, then use the symbols “!”, “?” and “#”, respectively.)
    To decrypt, convert the encrypted message into numbers C1,C2, . . ., and calculate Mi = Cdi mod pq,where d is an integer satisfying de ≡ 1 mod (p − 1)(q − 1). This will give you the message as a sequence of numbers less than 676, and you can then translate that back into English using the division algorithm as described above.
    We have received an important encrypted message – it reads FRWHVWNUTSHX. We know the
    message was encrypted using e = 257. In each of the following parts, show all of your working.
    (a) Determine the d we need to use to decrypt this message. (HINT: use the Euclidean algorithm
    to first solve 257x+(p−1)(q −1)y = 1 – you should then be able to determine d; think about
    it!)
    (b) Convert the encrypted message into a sequence of numbers less than 676.
    (c) Decrypt the message using your answers to the first two parts and convert into English.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Encryption

    Hello smithhall

    I have a solution - but I'm not confident that the coded letters are correct. I say this because there are clearly errors in the problem description. For example:
    For example, to convert DISCRETE into numbers we would do the following: DI–SC–RE–TE becomes
    D is 3, I is 8: so DI is 3 × 26 + 8 = 80.
    S is 18, C is 2: so SC is 18 × 26 + 2 = 470.
    R is 17, E is 4: so RE is 17 × 26 + 4 = 446.
    T is 19, E is 4: so TE is 19 × 26 + 4 = 498.
    Thus, DISCRETE would be written 80–470–446–498.
    This is obviously wrong: DI is 86, not 80. Such an elementary mistake in work where numerical accuracy is vital doesn't inspire confidence!

    Also
    Now calculate Ci = Mei mod pq for each i.
    should read:

    C_i = M_i^e\mod pq

    and
    To decrypt, convert the encrypted message into numbers C1,C2, . . ., and calculate Mi = Cdi mod pq,where d is an integer satisfying de ≡ 1 mod (p − 1)(q − 1).
    should again read

    M_i = C_i^d\mod pq

    It took me some time to discover this - having never seen this encryption before. These formulae are to be found, for example, at RSA - Wikipedia, the free encyclopedia.

    So I have to ask: is this sequence correct?
    We have received an important encrypted message – it reads FRWHVWNUTSHX.
    I'm not sure.

    Anyway, here are my answers.
    (a) Determine the d we need to use to decrypt this message. (HINT: use the Euclidean algorithm to first solve 257x+(p−1)(q −1)y = 1 – you should then be able to determine d; think about it!)
    I used the Euclidean algorithm and found d = 65. Can you do this OK?
    (b) Convert the encrypted message into a sequence of numbers less than 676.
    This is very straightforward: 147, 579, 568, 358, 512, 205. To save time and (hopefully) avoid the sort of arithmetic error above I used a look-up table in an Excel spreadsheet.
    (c) Decrypt the message using your answers to the first two parts and convert into English.
    This is the part where the arithmetic gets very difficult. Again I used the Excel spreadsheet, but even so it was very tricky because finding c^{65} \mod 679 can't be done in a single operation, because of overflow errors. In the end, I found I could calculate c^3 \mod 679 without causing errors. Then by careful manipulation of powers (I used 65 = 3\times 3\times 2\times 2 + 3\times 3\times 3 + 2), I obtained the following numbers: 147, 108, 92, 358, 512, 676, which being interpreted is: FREEODUNSTAZ.

    Not sure what that means, though!

    Spreadsheet attached.

    Grandad
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by Grandad View Post
    It took me some time to discover this - having never seen this encryption before.
    Grandad, I thought you knew eveything.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Still learning!

    Hello aidan
    Quote Originally Posted by aidan View Post
    Grandad, I thought you knew eveything.
    No, this stuff's only been around for about 30 years, and I'm much too old for that!

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. how and what is an encoding matrix?
    Posted in the Calculators Forum
    Replies: 4
    Last Post: July 4th 2011, 05:28 PM
  2. Encoding/Decoding Matrices
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 12th 2009, 03:45 AM
  3. Replies: 0
    Last Post: September 10th 2009, 01:43 AM
  4. encoding and decoding help
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 7th 2008, 09:44 AM
  5. Histogram encoding
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: March 30th 2006, 03:40 PM

Search Tags


/mathhelpforum @mathhelpforum