#!/bin/bash

# RSA.sh: toy implementation of the RSA algorithm, in shell script (bash).
# Everything is implemented using only bash constructions and builtins
# 
# It can generate RSA keys (15-bit) and encrypt/decrypt simple strings
# 
# Believe it or not, the slowest part of this script is the function
# get the ASCII code for a character (used in encryption)
#
# This "source code" is public domain. Do whatever you want with it
#
# Send comments or suggestions to pdiaz (AT) pedrodiaz [DOT] com
# Pedro Diaz. April 2005
#
#
#
# EXAMPLE USAGE:
#
# $ ./RSA.sh keygen
# Generating 15-bit public and private keys
# Please wait here while I call the locksmith...done
# 
# Your public key is : 136877231,11299
# Your private key is: 136877231,131681995
# 
# $ ./RSA.sh encrypt 136877231,11299 'Hello world!'
# 9642589 66355095 109029100 109029100 47620778 116845464 86960859 47620778 36274896 109029100 104043122 115209967
# 
# $ ./RSA.sh decrypt 136877231,131681995 '9642589 66355095 109029100 109029100 47620778 116845464 86960859 47620778 36274896 109029100 104043122 115209967'
# Hello world!
#
#
#
# An imaginary FAQ:
#
# Q - 15-bit keys?. Really?
# A - Actually, two 15-bit primes are used (p and q). The resulting product
#     (p*q) is about 30 bits. Since the way to crack (by brute force) RSA is 
#     factoring p*q, I guess one could say they are in fact 30-bit keys. 
#
#    
# Q - Can I increase the key length?
# A - Not much, if at all. All the arithmetic is done with bash builtins, 
#     which is done using CPU arithmetic instructions (no fancy 
#     arbitrary-precision library was used). This imposes a boundary on 
#     the size of the primes used in key generation. Using 15-bit primes
#     is very convenient, because their product is guaranteed to fit
#     in a 32-bit signed integer, which is what bash uses on my computer.
#     If you still want to try it, locate the variables b1 and b2 and
#     set the appropiate range. If you get negative values when encrypting,
#     the primes are too big (probably)
#
#
# Q - What's the point of all this?. Shouldn't you be studying or something?
# A - No point at all. Yes







# 
# Computes the binary expansion of a number. Doesn't
# work with n=0, but who cares ;-)
#
# Returns result in $BIN
function tobin() {
	local n=$1
	local tmp
	
	BIN=""
	while [ "$n" -ne "0" ]; do
		let tmp="$n % 2"
		BIN="$tmp $BIN"
		let n="$n/2"
	done
}


# Modular exponetiation. Implemented as in "Introduction to Algorithms"
# Cormen et al, 2nd edition. Pg 879
#
# Returns in $EXP
function modexp() {
	local a=$1
	local b=$2
	local m=$3
	local d=1
	local i
	local binb

	# binb is the binary expansion of b
	tobin $b
	binb=$BIN

	for i in $BIN; do
		let d="($d*$d) % m"
		if [ "$i" == 1 ]; then
			let d="($d*$a) % m"
		fi
	done

	EXP="$d"
}


# This function performs a Miller-Rabin primality test
function is_prime() {
	local n
	local p
	local q
	local k
	local a
	local res
	local j
	p=$1
	# n is p-1
	let n="$p -1"


	# Write n as q*2^k, with q odd
	k=0
	q="$n"
	let rem="$q % 2"
	while [ "$rem" == "0" ]; do
		let k="$k + 1"
		let q="$q/2"
		let rem="$q % 2"
	done

	# Select a random integer a, 1 < a < n
	let a="$RANDOM % $n"

	# If a^q mod p == 1 then p maybe prime
	modexp $a $q $p
	res=$EXP
	if [ "$res" == "1" ]; then
		return 1
	fi

	# For j=0 to k-1 do:
	#    if a^(q*2^j) mod p == n then p maybe prime
	j=0
	exp="$q"
	while [ "$j" -lt "$k" ]; do
		modexp $a $exp $p
		res="$EXP"
		if [ "$res" == "$n" ]; then
			return 1
		fi

		let j="$j +1"
		# Calculate the next exponent
		let exp="$exp*2"

	done
	
	return 0
}

# Calculates the multiplicative inverse of a given number n in some module
# Assumes that the modulo is greater than the number. Uses the
# extended Euclid's algorithm
#
# Returns the inverse on $INV
function mult_inv() {
	local n="$1"
	local m="$2"
	local i
	local i1
	local i2
	# These arrays are the columns of the
	# extended euclid algorithm's table.
	# I know that only the last two rows
	# are needed, but anyways..is easier
	# this way
	local -a q
	local -a r
	local -a u


	# Init the table
	q[0]="-" # To prevent accidental use
	q[1]="-"
	r[0]="$m"
	r[1]="$n"
	v[0]="0"
	v[1]="1"
	
	# Iterate
	i=2
	while (true); do
		let i1="$i -1"
		let i2="$i -2"
		
		# q[i]=r[i-2]/r[i-1]
		let q[$i]="${r[$i2]}/${r[$i1]}"

		# r[i]=r[i-2] mod r[i-1]
		let r[$i]="${r[$i2]} % ${r[$i1]}"

		# v[i]=v[i-2] - q[i]*v[i-1]
		let v[$i]="${v[$i2]} - (${q[$i]}*${v[$i1]})"

		# If r[i]==1 exit
		if [ "${r[$i]}" == "1" ]; then
			break
		fi
		
		# i = i +1
		let i="$i +1"
	done

	# bash does not care about negative
	# numbers modulo something, but we
	# do
	let INV="${v[$i]} % $m"
	if [ "$INV" -lt "0" ]; then
		let INV="$INV + $m"
	fi
		
}

# Gets a random prime number
#
# Returns it in $PRIME
function get_rand_prime() {
	local tmp
	local tmp2
	local res
	
	# Get a randon odd number, in the requested range
	tmp=1
	while [ "$tmp" -le "$1" ] || [ "$tmp" -ge "$2" ]; do
		# This is rude. I know
		let tmp="$1+ (($RANDOM*$RANDOM*$RANDOM) % ($2-$1))"
		let tmp2="$tmp % 2"
		if [ "$tmp2" == "0" ]; then
			let tmp="$tmp +1"
		fi
	done
	
	# Test for primality
	while (true); do
		is_prime $tmp
		res=$?
		if [ "$res" == "1" ]; then
			break;
		fi
		let tmp="$tmp +2"
	done
	
	PRIME=$tmp
}
	

# This function generates an RSA keypair.
#
# Returns in variables PUBKEY,PRIVKEY
function generate_keys() {
	local q
	local p
	local n
	local e
	local d
	local phi
	local tmp
	local tmp2
	# 15-bit primes
	local b1=8192 
	local b2=16384 

	# Get a prime
	get_rand_prime $b1 $b2
	p=$PRIME

	q=$p
	while [ "$p" == "$q" ]; do
		# Get another prime
		get_rand_prime $b1 $b2
		q=$PRIME
	done


	# The public key can be determined now

	# n
	let n="$p * $q"

	# phi
	let tmp="$p -1"
	let tmp2="$q -1"
	let phi="$tmp * $tmp2"

	# We have to find an exponent e such that
	# gcd(phi,e)==1. We just take the easy road
	# and generate a prime
	get_rand_prime $b1 $b2
	e=$PRIME

	# Pubkey is ready
	PUBKEY="$n,$e"


	# To determine the secret key we have to find
	# d, the decryption exponent. This exponent is
	# the multiplicative inverse of e modulo phi
	mult_inv $e $phi
	d=$INV
	PRIVKEY="$n,$d"
}



# Given a character, it returns its ASCII code. I don't
# know any other way to do this in pure bash other than doing
# a search over the ASCII table. I'd like to do this
# with a binary search, but the < > string comp. operators
# seem to work weird (\011 >  \012 , but "A" < "B" )

function char_to_ascii() {
	local c="${1:0:1}"
	local i
	local oct
	local testc
	# We start from printable characters
	i=32
	while [ "$i" -le 255 ]; do
		oct=`printf "%03o" $i`
		testc=`printf "\\\\${oct}"`
		if [ "$testc" == "$c" ]; then
			return $i
		fi

		let i="$i +1"
	done
}



# Encrypts (and decrypts) a given string. 
# 
# Returns the ciphertext/plaintext on RSA
function encrypt() {
	local n="$1"
	local e="$2"
	local s="$3"
	local i
	local c
	
	# IDEAL SITUATION: The plaintext is separated in several
	# fixed-length multibyte groups, each with value < n. 
	# These groups are then encrypted/decrypted.

	# THE CRUDE REALITY: We encrypt independently
	# each character

	RSA=""
	for i in $s ; do
		# Encrypt/decrypt it
		modexp $i $e $n
		RSA="$RSA $EXP"
	done

}

# Prints usage of this script
function print_usage() {
	echo "RSA.sh. Pedro Diaz (pdiaz@pedrodiaz.com)"
	echo "Usage:"
	echo -e "\tTo generate a 15-bit RSA keypair : $0 keygen"
	echo -e "\tTo encrypt a string              : $0 encrypt key string"
	echo -e "\tTo decrypt a string              : $0 decrypt key string"
	echo
	echo "key is either the public or private key, in the same format as returned by \"$0 keygen\". "
	echo "Remember to quote the string when encrypting or decrypting"
	echo
	echo "Never, ever, use this program to encrypt sensitive data. I mean it. Really"
	
}


# MAIN PROGRAM
if [ "$1" == "" ]; then
	print_usage
	exit 1
elif [ "$1" == "keygen" ]; then
	echo "Generating 15-bit public and private keys"
	echo -n "Please wait here while I call the locksmith..."
	generate_keys
	echo "done"
	echo
	echo "Your public key is : $PUBKEY"
	echo "Your private key is: $PRIVKEY"
elif [ "$1" == "encrypt" ]; then
	
	if [ "$2" == "" ] || [ "$3" == "" ]; then
		print_usage
		exit 1
	fi
	
	# Get the components of the key
	pub_n=""
	pub_e=""
	for i in ${2/,/ } ; do
		if [ "$pub_n" == "" ]; then
			pub_n="$i"
		else
			pub_e="$i"
		fi
	done
	

	# Transform the text to an ascii string
	len="${#3}"
	string=""
	i=0;
	while [ "$i" -lt "$len" ]; do
		# Get the character
		c=${3:$i:1}

		# Get its ASCII number
		char_to_ascii "$c"
		a="$?"

		# Append it to our string
		string="$string $a"
		
		# Advance
		let i="$i +1"
	done

	# call encrypt
	encrypt $pub_n $pub_e "$string"
	
	# Show the result
	echo $RSA

elif [ "$1" == "decrypt" ]; then
	
	if [ "$2" == "" ] || [ "$3" == "" ]; then
		print_usage
		exit 1
	fi
	
	# Get the components of the key
	pub_n=""
	pub_d=""
	for i in ${2/,/ } ; do
		if [ "$pub_n" == "" ]; then
			pub_n="$i"
		else
			pub_d="$i"
		fi
	done
	
	text="$3"
	
	# call decrypt
	encrypt $pub_n $pub_d "$text"

	# Convert from ascii to character
	for i in $RSA; do
		oct=`printf "%03o" $i`
		c=`printf "\\\\$oct"`
		echo -n "$c"
	done
	echo
fi