rsa in bash (with bc), a few years old

rsa.sh

#!/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