Skip to content

Instantly share code, notes, and snippets.

@onli
Created January 8, 2014 17:04
Show Gist options
  • Save onli/8320277 to your computer and use it in GitHub Desktop.
Save onli/8320277 to your computer and use it in GitHub Desktop.
rsa in bash (with bc), a few years old
#!/bin/bash
getPrim() {
local range="$1"
local prim=$(getRandom $range)
until [[ $prim -gt 1 ]] && isPrim $prim;do
prim=$(getRandom $range)
done
echo $prim
return 0
}
#Miller-Rabin-Test
isPrim() {
local prim=$1
if [[ $(echo "$prim % 2" | bc) -eq 0 ]];then
return 1
fi
#won't find an "a" for them:
if [[ $prim -eq 3 ]] || [[ $prim -eq 5 ]];then
return 0
fi
prim_range=${#prim}
local i=0
while [[ $i -lt 10 ]];do
local a=$(getRandom $(($RANDOM % (prim_range + 1) )) )
until [[ $(echo "$a < ($prim - 2) && $a > 2" | bc) -eq 1 ]];do
a=$(getRandom $(($RANDOM % (prim_range + 1) )) )
done
if isWitness $prim $a;then
return 1
fi
let i++
done
return 0
}
function isWitness() {
prim=$1
a=$2
prim_minus_one=$(echo "$prim - 1" | bc)
test=1
local i=${#prim_minus_one}
i=$(($i - 1))
while [[ $i -ge 0 ]];do
x=$test
test=$(echo "$x^2 % $prim" | bc)
if [[ $test -eq 1 ]] && [[ $x -ne 1 ]] && [[ $x -ne $prim_minus_one ]];then
return 0
fi
let i--
done
test=$(powmod $a $prim_minus_one $prim)
if [[ $test -ne 1 ]];then
return 0
else
return 1
fi
}
setBasics() {
local range="$1"
local try="$2"
if [[ -z "$range" ]];then
#the length of sqrt(m) for p and q fits to the necessary length of n
range=$(echo "sqrt($m)" | bc)
range=${#range}
fi
if [[ -z "$try" ]];then
try=1
fi
doBasics $range $try
#bash's comparison won't work with big numbers
until [[ $(echo "$n > $m" | bc) -eq 1 ]];do
let try++
if [[ $try -gt $(($range * 10)) ]] || [[ ${#n} -lt $(( ${#m} -2 )) ]];then
let range++
try=1
fi
doBasics $range $try
done
}
function doBasics() {
local range="$1"
local try="$2"
#two primenumbers
p=$(getPrim $range)
q=$(getPrim $range)
until [[ p -ne q ]];do
p=$(getPrim $range)
q=$(getPrim $range)
done
#RSA-Modul
n=$(echo "$p*$q" | bc -l)
#eulersche
phi=$(echo "($p-1)*($q-1)" | bc -l)
}
#choose e coprime to phi
getPublicKey() {
local e=$(($RANDOM))
until [[ $(echo "$e < $phi" | bc) -eq 1 ]];do
e=$(($RANDOM))
done
local i=2
while [[ $(echo "$i < $e" | bc) -eq 1 ]];do
if [[ $(echo "$phi % $i" | bc ) -eq 0 ]] && [[ $(echo "$e % $i" | bc) -eq 0 ]];then
getPublicKey
exit
fi
let i++
done
echo $e
}
getPrivateKey() {
local result=($(extended_euclid $e $phi))
local d=${result[0]}
until [[ $d -gt 0 ]];do
d=$(echo "$d+$phi" | bc -l)
done
echo $d
}
function extended_euclid() {
a=$1
b=$2
local x=0
local lastx=1
local y=1
local lasty=0
while [[ $b -ne 0 ]];do
local quotient=$(echo "$a / $b" | bc)
local temp=$b
b=$(echo "$a % $b" | bc)
a=$temp
temp=$x
x=$(echo "$lastx - ($quotient * $x)" | bc)
lastx=$temp
temp=$y
y=$(echo "$lasty - ($quotient * $y)" | bc)
lasty=$temp
done
local result=($lastx $lasty $a)
echo "${result[*]}";
return 0
}
#a^b%m: Square & Multiply
powmod() {
local a=$1
local b=$2
local mod=$3
local i=0
local res=1
#b in binary for binary exponentiation
b=$(echo "ibase=10;obase=2; $b" | bc)
while [[ $i -lt ${#b} ]];do
res=$(echo "$res^2 * $a ^ ${b:$i:1} % $mod" | bc)
let i++
done
echo $res
}
getRandom() {
local range="$1"
if [[ -z "$range" ]];then
range=$RANDOM
fi
local r=$((RANDOM % 10))
while [[ $r -eq 0 ]];do
r=$((RANDOM % 10))
done
local i=1
while [[ $i -lt $range ]];do
local temp=$((RANDOM % 10))
r=${r}${temp}
let i++
done
echo $r
}
encrypt() {
local m="$1"
local c=$(powmod $m $e $n)
echo "$c"
}
decrypt() {
local c="$1"
local m=$(powmod $c $d $n)
echo "$m"
}
export BC_LINE_LENGTH=0
m=91011121314151617181920212223242526272829
old_m=$m
setBasics
e=$(getPublicKey)
echo "Public Key: ($e, $n)"
d=$(getPrivateKey)
echo "Private Key: ($d, $n)"
echo
c=$(encrypt "$m")
echo "c: $c"
m=$(decrypt "$c")
echo "m: $m"
if [[ $m -ne $old_m ]];then
echo "Error: Wrong message decrypted:" >&2
echo "p: $p" >&2
echo "q: $q" >&2
echo "Public Key: ($e, $n)" >&2
echo "Private Key: ($d, $n)" >&2
echo "c: $c" >&2
echo "m: $m" >&2
fi
#Ausgabe
#onli@Fallout:~$ uni/ts/rsa.sh
#p: 783057321236353042573
#q: 444786834379004491147
#Public Key: (2969, 348293587050020677086428785700425092601231)
#Private Key: (137252777651911145904238835165856311899289, 348293587050020677086428785700425092601231)
#
#c: 134886886292723664083288725067434182648518
#m: 91011121314151617181920212223242526272829
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment