rsa.bc

 

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