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