Archive

Archive for the ‘Encryption’ Category

An encrypted message for you… The math behind the RSA… Step-by-step…

So, you’ve come here because you’re curious about my encrypted message 😀 This is to show the output of application I wrote few years back during my undergrad in Computer Science based on the RSA Encryption. So, here’s the encrypted message:

1142022-35601-1-64-1-6020454-8000-5985272-1331-2299968-1753099-
1873700-4200047-1227254-343-3740201-752788-3764509-32768-2406104-
2874958-1771561-238328-1-4830182-3014099-8000-856850-1-373248-
900525-2207342-1985915-27-9261-912673-9261-226981-2689412-945762-
64-5509130-4680829-4567886-729-3969407-1873700-9261-3978260-
4869518-1331-8000-5130977-2197-8-4913-74088-1367631-941192-
3957527-6859-2779352-1-68921-3129271-4913-64-3734521-2523631-
3553443-2763573-6190443-5037509-1-5347086-729-6226022-68921-2406104

Information Hiding is a very old technique used to hide secrets 🙂 So, I use RSA to encrypt messages…

#### RSA Public Key Creation Process ####

-> Configuring random prime numbers
        P = 2591
        Q = 2411

-> Calculating public keys

   N = P * Q; N = 6246901
-> FI = (P-1) * (Q-1); FI = 6241900

-> Calculating (E)
           While MCD(n >= 2 , 6241900) != 1
           MCD(2 , 6241900) = 2
           MCD(3 , 6241900) = 1 Correct!
          E = 3

       Public Key (N,E) = (6246901 , 3)

#### RSA Private Key Creation Process ####

-> Calculating private keys
         Initializing (p1,p2,p3) = (1, 0 , FI(n))
         Initializing (q1,q2,q3) = (0, 1 ,  E  ))
         While q3 != 0
             quoc = p3 / q3
             (t1,t2,t3) = (p1,p2,p3) - quoc * (q1,q2,q3)
             After, arrange the values:
             (p1,p2,p3) = (q1,q2,q3)
             (q1,q2,q3) = (t1,t2,t3)

           (3 <> 0) , then:
             quoc = 6241900 / 3 = 2080633
             (t1,t2,t3) = (0,1,3) - 2080633 * (1,-2080633,1) = (1,-2080633,1)
             (p1,p2,p3) = (1,-2080633,1)
             (q1,q2,q3) = (1,-2080633,1)

           (1 <> 0) , then:
             quoc = 3 / 1 = 3
             (t1,t2,t3) = (1,-2080633,1) - 3 * (-3,6241900,0) = (-3,6241900,0)
             (p1,p2,p3) = (-3,6241900,0)
             (q1,q2,q3) = (-3,6241900,0)

         q3 is zero(0). Now, verify the value of p2. In case of negative, invert it by summing it with FI. (represent the negative number of z(n) by a positive.)

         u2 = -2080633;
          Since u2 is negative, we have:
          D = u2 + FI; D = -2080633 + 6241900 = 4161267

      Private Key (N,D) = (6246901, 4161267);

#### RSA Keys Summary ####

Public Key (N, E) = (6246901, 3)
Private Key (N, D) = (6246901, 4161267)

The public key is used to give to the receiving party. The Secret key is kept in secret 🙂 Ready to see what I want during the Hacker Dojo Day??? Consider the 2 RSA Keys above and follow the calculations to the SECRET MESSAGE 😀

#### Decoding the Message ####

-> Setting the private key
(N , D) = (6246901 , 4161267)

-> Decripting each block
Ascii(x) = x ^ D mod N

Ascii(1142022) = 1142022 ^ 4161267 mod 6246901 = 1771
Ascii(35601) = 35601 ^ 4161267 mod 6246901 = 972
Ascii(1) = 1 ^ 4161267 mod 6246901 = 1
Ascii(64) = 64 ^ 4161267 mod 6246901 = 4
Ascii(1) = 1 ^ 4161267 mod 6246901 = 1
Ascii(6020454) = 6020454 ^ 4161267 mod 6246901 = 99201
Ascii(8000) = 8000 ^ 4161267 mod 6246901 = 20
Ascii(5985272) = 5985272 ^ 4161267 mod 6246901 = 82082
Ascii(1331) = 1331 ^ 4161267 mod 6246901 = 11
Ascii(2299968) = 2299968 ^ 4161267 mod 6246901 = 132
Ascii(1753099) = 1753099 ^ 4161267 mod 6246901 = 200
Ascii(1873700) = 1873700 ^ 4161267 mod 6246901 = 201
Ascii(4200047) = 4200047 ^ 4161267 mod 6246901 = 13218
Ascii(1227254) = 1227254 ^ 4161267 mod 6246901 = 319
Ascii(343) = 343 ^ 4161267 mod 6246901 = 7
Ascii(3740201) = 3740201 ^ 4161267 mod 6246901 = 20820
Ascii(752788) = 752788 ^ 4161267 mod 6246901 = 1215
Ascii(3764509) = 3764509 ^ 4161267 mod 6246901 = 1581
Ascii(32768) = 32768 ^ 4161267 mod 6246901 = 32
Ascii(2406104) = 2406104 ^ 4161267 mod 6246901 = 134
Ascii(2874958) = 2874958 ^ 4161267 mod 6246901 = 17120
Ascii(1771561) = 1771561 ^ 4161267 mod 6246901 = 121
Ascii(238328) = 238328 ^ 4161267 mod 6246901 = 62
Ascii(1) = 1 ^ 4161267 mod 6246901 = 1
Ascii(4830182) = 4830182 ^ 4161267 mod 6246901 = 6205
Ascii(3014099) = 3014099 ^ 4161267 mod 6246901 = 210
Ascii(8000) = 8000 ^ 4161267 mod 6246901 = 20
Ascii(856850) = 856850 ^ 4161267 mod 6246901 = 3132
Ascii(1) = 1 ^ 4161267 mod 6246901 = 1
Ascii(373248) = 373248 ^ 4161267 mod 6246901 = 72
Ascii(900525) = 900525 ^ 4161267 mod 6246901 = 2052
Ascii(2207342) = 2207342 ^ 4161267 mod 6246901 = 1420
Ascii(1985915) = 1985915 ^ 4161267 mod 6246901 = 12001
Ascii(27) = 27 ^ 4161267 mod 6246901 = 3
Ascii(9261) = 9261 ^ 4161267 mod 6246901 = 21
Ascii(912673) = 912673 ^ 4161267 mod 6246901 = 97
Ascii(9261) = 9261 ^ 4161267 mod 6246901 = 21
Ascii(226981) = 226981 ^ 4161267 mod 6246901 = 61
Ascii(2689412) = 2689412 ^ 4161267 mod 6246901 = 3221
Ascii(945762) = 945762 ^ 4161267 mod 6246901 = 620
Ascii(64) = 64 ^ 4161267 mod 6246901 = 4
Ascii(5509130) = 5509130 ^ 4161267 mod 6246901 = 2011
Ascii(4680829) = 4680829 ^ 4161267 mod 6246901 = 32172
Ascii(4567886) = 4567886 ^ 4161267 mod 6246901 = 1971
Ascii(729) = 729 ^ 4161267 mod 6246901 = 9
Ascii(3969407) = 3969407 ^ 4161267 mod 6246901 = 9207
Ascii(1873700) = 1873700 ^ 4161267 mod 6246901 = 201
Ascii(9261) = 9261 ^ 4161267 mod 6246901 = 21
Ascii(3978260) = 3978260 ^ 4161267 mod 6246901 = 41321
Ascii(4869518) = 4869518 ^ 4161267 mod 6246901 = 682
Ascii(1331) = 1331 ^ 4161267 mod 6246901 = 11
Ascii(8000) = 8000 ^ 4161267 mod 6246901 = 20
Ascii(5130977) = 5130977 ^ 4161267 mod 6246901 = 6211
Ascii(2197) = 2197 ^ 4161267 mod 6246901 = 13
Ascii(8) = 8 ^ 4161267 mod 6246901 = 2
Ascii(4913) = 4913 ^ 4161267 mod 6246901 = 17
Ascii(74088) = 74088 ^ 4161267 mod 6246901 = 42
Ascii(1367631) = 1367631 ^ 4161267 mod 6246901 = 111
Ascii(941192) = 941192 ^ 4161267 mod 6246901 = 98
Ascii(3957527) = 3957527 ^ 4161267 mod 6246901 = 132170
Ascii(6859) = 6859 ^ 4161267 mod 6246901 = 19
Ascii(2779352) = 2779352 ^ 4161267 mod 6246901 = 72052
Ascii(1) = 1 ^ 4161267 mod 6246901 = 1
Ascii(68921) = 68921 ^ 4161267 mod 6246901 = 41
Ascii(3129271) = 3129271 ^ 4161267 mod 6246901 = 32140
Ascii(4913) = 4913 ^ 4161267 mod 6246901 = 17
Ascii(64) = 64 ^ 4161267 mod 6246901 = 4
Ascii(3734521) = 3734521 ^ 4161267 mod 6246901 = 1972
Ascii(2523631) = 2523631 ^ 4161267 mod 6246901 = 1013
Ascii(3553443) = 3553443 ^ 4161267 mod 6246901 = 214
Ascii(2763573) = 2763573 ^ 4161267 mod 6246901 = 9154
Ascii(6190443) = 6190443 ^ 4161267 mod 6246901 = 1441
Ascii(5037509) = 5037509 ^ 4161267 mod 6246901 = 32150
Ascii(1) = 1 ^ 4161267 mod 6246901 = 1
Ascii(5347086) = 5347086 ^ 4161267 mod 6246901 = 4814
Ascii(729) = 729 ^ 4161267 mod 6246901 = 9
Ascii(6226022) = 6226022 ^ 4161267 mod 6246901 = 1481
Ascii(68921) = 68921 ^ 4161267 mod 6246901 = 41
Ascii(2406104) = 2406104 ^ 4161267 mod 6246901 = 134

-> Complete message in ASCII
177197214199201208208211132200201132183197208201215158132134171201216216205210203132172205214201200
132197216132216204201132172197199207201214132168211206211132174211198132170197205214132140174197210
132149154144132150148149148141134
-> Original Message
Marcello de Sales: "Breaking the rules"

This is a simple notion of an inverse function. I first implemented this during my undergrad school in Computer Science… So, here’s the original encryption process. I’m looking for a Job, this is my “hacking” way of doing it :P… Marcello de Sales: “Breaking the rules”. Here’s how I calculated the encrypted message.

-> Original Message
Marcello de Sales: "Breaking the rules"

-> Setting the receiver's public key
(N , E) = (6246901 , 3)

-> Transforming the message to ASCII code
177197214199201208208211132200201132183197208201215158132134171201216216205210203132172205214201200
132197216132216204201132172197199207201214132168211206211132174211198132170197205214132140174197210
132149154144132150148149148141134

-> Configuring randomly selected blocks from the ASCII message
Bloco(x) = x ^ E mod N

Block(1771) = 1771 ^ 3 mod 6246901 = 1142022
Block(972) = 972 ^ 3 mod 6246901 = 35601
Block(1) = 1 ^ 3 mod 6246901 = 1
Block(4) = 4 ^ 3 mod 6246901 = 64
Block(1) = 1 ^ 3 mod 6246901 = 1
Block(99201) = 99201 ^ 3 mod 6246901 = 6020454
Block(20) = 20 ^ 3 mod 6246901 = 8000
Block(82082) = 82082 ^ 3 mod 6246901 = 5985272
Block(11) = 11 ^ 3 mod 6246901 = 1331
Block(132) = 132 ^ 3 mod 6246901 = 2299968
Block(200) = 200 ^ 3 mod 6246901 = 1753099
Block(201) = 201 ^ 3 mod 6246901 = 1873700
Block(13218) = 13218 ^ 3 mod 6246901 = 4200047
Block(319) = 319 ^ 3 mod 6246901 = 1227254
Block(7) = 7 ^ 3 mod 6246901 = 343
Block(20820) = 20820 ^ 3 mod 6246901 = 3740201
Block(1215) = 1215 ^ 3 mod 6246901 = 752788
Block(1581) = 1581 ^ 3 mod 6246901 = 3764509
Block(32) = 32 ^ 3 mod 6246901 = 32768
Block(134) = 134 ^ 3 mod 6246901 = 2406104
Block(17120) = 17120 ^ 3 mod 6246901 = 2874958
Block(121) = 121 ^ 3 mod 6246901 = 1771561
Block(62) = 62 ^ 3 mod 6246901 = 238328
Block(1) = 1 ^ 3 mod 6246901 = 1
Block(6205) = 6205 ^ 3 mod 6246901 = 4830182
Block(210) = 210 ^ 3 mod 6246901 = 3014099
Block(20) = 20 ^ 3 mod 6246901 = 8000
Block(3132) = 3132 ^ 3 mod 6246901 = 856850
Block(1) = 1 ^ 3 mod 6246901 = 1
Block(72) = 72 ^ 3 mod 6246901 = 373248
Block(2052) = 2052 ^ 3 mod 6246901 = 900525
Block(1420) = 1420 ^ 3 mod 6246901 = 2207342
Block(12001) = 12001 ^ 3 mod 6246901 = 1985915
Block(3) = 3 ^ 3 mod 6246901 = 27
Block(21) = 21 ^ 3 mod 6246901 = 9261
Block(97) = 97 ^ 3 mod 6246901 = 912673
Block(21) = 21 ^ 3 mod 6246901 = 9261
Block(61) = 61 ^ 3 mod 6246901 = 226981
Block(3221) = 3221 ^ 3 mod 6246901 = 2689412
Block(620) = 620 ^ 3 mod 6246901 = 945762
Block(4) = 4 ^ 3 mod 6246901 = 64
Block(2011) = 2011 ^ 3 mod 6246901 = 5509130
Block(32172) = 32172 ^ 3 mod 6246901 = 4680829
Block(1971) = 1971 ^ 3 mod 6246901 = 4567886
Block(9) = 9 ^ 3 mod 6246901 = 729
Block(9207) = 9207 ^ 3 mod 6246901 = 3969407
Block(201) = 201 ^ 3 mod 6246901 = 1873700
Block(21) = 21 ^ 3 mod 6246901 = 9261
Block(41321) = 41321 ^ 3 mod 6246901 = 3978260
Block(682) = 682 ^ 3 mod 6246901 = 4869518
Block(11) = 11 ^ 3 mod 6246901 = 1331
Block(20) = 20 ^ 3 mod 6246901 = 8000
Block(6211) = 6211 ^ 3 mod 6246901 = 5130977
Block(13) = 13 ^ 3 mod 6246901 = 2197
Block(2) = 2 ^ 3 mod 6246901 = 8
Block(17) = 17 ^ 3 mod 6246901 = 4913
Block(42) = 42 ^ 3 mod 6246901 = 74088
Block(111) = 111 ^ 3 mod 6246901 = 1367631
Block(98) = 98 ^ 3 mod 6246901 = 941192
Block(132170) = 132170 ^ 3 mod 6246901 = 3957527
Block(19) = 19 ^ 3 mod 6246901 = 6859
Block(72052) = 72052 ^ 3 mod 6246901 = 2779352
Block(1) = 1 ^ 3 mod 6246901 = 1
Block(41) = 41 ^ 3 mod 6246901 = 68921
Block(32140) = 32140 ^ 3 mod 6246901 = 3129271
Block(17) = 17 ^ 3 mod 6246901 = 4913
Block(4) = 4 ^ 3 mod 6246901 = 64
Block(1972) = 1972 ^ 3 mod 6246901 = 3734521
Block(1013) = 1013 ^ 3 mod 6246901 = 2523631
Block(214) = 214 ^ 3 mod 6246901 = 3553443
Block(9154) = 9154 ^ 3 mod 6246901 = 2763573
Block(1441) = 1441 ^ 3 mod 6246901 = 6190443
Block(32150) = 32150 ^ 3 mod 6246901 = 5037509
Block(1) = 1 ^ 3 mod 6246901 = 1
Block(4814) = 4814 ^ 3 mod 6246901 = 5347086
Block(9) = 9 ^ 3 mod 6246901 = 729
Block(1481) = 1481 ^ 3 mod 6246901 = 6226022
Block(41) = 41 ^ 3 mod 6246901 = 68921
Block(134) = 134 ^ 3 mod 6246901 = 2406104

-> Encrypted Message
1142022-35601-1-64-1-6020454-8000-5985272-1331-2299968-1753099-1873700-4200047-1227254-343-3740201-752788-3764509-32768-2406104-2874958-1771561-238328-1-4830182-3014099-8000-856850-1-373248-900525-2207342-1985915-27-9261-912673-9261-226981-2689412-945762-64-5509130-4680829-4567886-729-3969407-1873700-9261-3978260-4869518-1331-8000-5130977-2197-8-4913-74088-1367631-941192-3957527-6859-2779352-1-68921-3129271-4913-64-3734521-2523631-3553443-2763573-6190443-5037509-1-5347086-729-6226022-68921-2406104
Categories: Encryption, RSA
%d bloggers like this: