#!/usr/bin/bc -q # The message "HELLO" in ASCII is the number: 72 69 76 76 79 # Note! The message number must be smaller than "n"! # So instead of ASCII, use A=1, B=2, C=3, ...: # "HELLO is then: 8 5 12 12 15. # Next we will block the message as character pairs: # HELLO --> HE LL O\0 --> 0805 1212 1500 # # If we pick p * q = n big enough, you can just use pairs of ASCII # values for the blocks. In this case, the message "HELLO CLASS!\n" # becomes: 7269 7676 7932 6776 6583 8333 1000 # For this to work, you can limit yourself to ASCII values smaller # than an upper-case 'Z' (so n > 9090) or use all ASCII (n >127127), # assuming your message is broken into 2 byte blocks. # # Here are some primes (from http://primes.utm.edu/lists/small/1000.txt): # 2 3 5 7 11 13 17 19 23 29 # 31 37 41 43 47 53 59 61 67 71 # 73 79 83 89 97 101 103 107 109 113 # 127 131 137 139 149 151 157 163 167 173 # 179 181 191 193 197 199 211 223 227 229 # 233 239 241 251 257 263 269 271 277 281 # 283 293 307 311 313 317 331 337 347 349 # 353 359 367 373 379 383 389 397 401 409 # 419 421 431 433 439 443 449 457 461 463 # 467 479 487 491 499 503 509 521 523 541 # 547 557 563 569 571 577 587 593 599 601 # 607 613 617 619 631 641 643 647 653 659 # 661 673 677 683 691 701 709 719 727 733 # 739 743 751 757 761 769 773 787 797 809 # 811 821 823 827 829 839 853 857 859 863 # 877 881 883 887 907 911 919 929 937 941 # 947 953 967 971 977 983 991 997 # # (If you limit your messages to ASCII < 'Z', the smallest primes # you can use are 97 and 101 for p and q.) # The message, as three blocks: m[0] = 0805 m[1] = 1212 m[2] = 1500 # Pick two prime numbers p and q (2^n+1 primes are best): p = 37 q = 53 # Compute the product n: n = p * q # Compute Euler's Totient function of n: t = (p-1) * (q-1) # Pick one of the keys, say the public (encrypt) key "e": e = 7 # Compute the matching (private or decrypt) key "d": define f(e,t) { auto i i = 0 while ( ((i*e) % t) != 1 ) i += 1 return i } d = f(e,t) # Note! bc doesn't show leading zeros! print "\np=", p, ", q=", q, ", n=", n, ", t=", t, ", e=(", e, ",", n, "), " print "d=(", d, ",", n, ")\n\n" # Encrypt message using (e,n) key (result is cyphertext): c[0] = (m[0] ^ e) % n c[1] = (m[1] ^ e) % n c[2] = (m[2] ^ e) % n print "plaintext (\qHELLO\q): ", m[0], " ", m[1], " ", m[2], "\n\n" print "cyphertext: ", c[0], " ", c[1], " ", c[2], "\n\n" # Recover plaintext from cyphertext using (d,n) key: r[0] = (c[0] ^ d) % n r[1] = (c[1] ^ d) % n r[2] = (c[2] ^ d) % n print "Recovered (decrypted) plaintext : " print r[0], " ", r[1], " ", r[2], "\n\n" quit