rsa.sh
Wednesday, 8. January 2014
Vor ein paar Jahren versuchte man mir zu erklären, wie RSA funktioniert. Als Übung - und mit der üblichen Warnung, unseren Code nie zu benutzen - sollten wir es selbst implementieren, denn nur dann wird es verstanden. Machte ich mit Freude, natürlich in Bash, einfach weil ich es konnte. Und ich noch heute grinsen muss beim Gedanken an die Schimpfworte, die der Tutor bei der Bewertung benutzt haben müsste (wenn ich mich richtig erinnere, bekam ich sogar die volle Punktzahl - was mich dann doch überraschte).
War mir sicher, das hier verbloggt zu haben, konnte es aber (anlässlich noqqes Implementierung) nicht mehr finden. Daher, uneditiert aus der Abgabemail (oder hier als gist):
#!/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
onli blogging am : Mein Rückblick aufs Studium, Teil 1: Bachelor Informatik TU Darmstadt
Vorschau anzeigen