Download rsa.bc source file
#!/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 print 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