shgeta/main.md

## main.md

      
    Raw
  

              main.md
            
          
    shell scriptで(opensslを使わないで)文字列をrsa公開鍵で暗号化する。

概要

rsaの勉強のためshellscriptで全部やってみる。
公開鍵はファイルフォーマットが単純なssh-rsaをつかう。
復号はここでは行わない。opensslなどで行う。
メモ


OCTET STRINGは8bit毎のデータのこと。大抵の場合１バイト8bitなので、だいたいバイト列のこと。

制限


公開鍵の長さは8で割り切れるものとする。

TODO


todo

仕様

ssh-rsa公開鍵のパースは別を参照
暗号化に必要なものは、暗号化する文字列、公開鍵中のe,公開鍵中のn (modulo?)
暗号化方法は「RSA PKCS#1 v1.5暗号」
pkcs#1で定義されるようにランダムのバイトで埋めてパディングする。まったく同一の平文を同じeを持つ複数の公開鍵で暗号化したものをeの数以上集めると平文が解析できる問題に対応するためらしい。
べき乗余を求める。(<パディング済みの平文をネットワークバイトオーダーで数字にしたもの。> ^ e ) % n
最後に、扱いやすいようにbase64をかける。
使い方

rsaencrypt <暗号化したい文字列> <ssh-rsa公開鍵の文字列>
暗号化されたものがbase64されて出てくる。
例
rsaencrypt "message" "ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQDNckEuuAeiPesx99s/ivWoXQGdJIMKRl0I0HiSLMCdK/dUrXy5ycyy51cEtv0t/AGQCkAxqiYBCWiVhLV/1qpZuONL9UT8cTa4TO749lFVaucxLNN7nvUtbtA4InKqRjsjqK27vCzyWxiMVIMX0jNpD0rPCwkTK2Ja6knCRN7kA2c3UyNmX4IoQ0xqT0vaUNuxtOe9SkmT3DLizDMbYByzJWVgotbZfOu1QbbClpLt/TbDd5l3fcGNsRzT8Cnd8zdvXk5ZsiUDKKhynvA4Tt/LN9LjZgxTyoEYJewYzf51E8gH057A9zXguBTTAiHMgD8xgeGzh4AVEEFJ1ZO6oCft Guest@shigeta-no-MacBook-Pro.local"
結果
jSS9OzYlOpPDR9+lLWObL3QaIV5ehbk6PO6MTIoUoYZ5E1r8xuu6a/MWn/IpD6hK8D5D3sAjNT9fJ4YK7E8wAeqiyN57CKDLaG5Rh3fjuETrkO0ZHUhnthOXp1YDYSRHRx8e/vWKM+Fisi6q8Ym7iTX2KUoPhcQ1iH+hypmncnrGUbRo3XB8/34hO6HRHF5WEItT8m2pVFnI8bvi+HYxNtX7Dh0BzNvW4KT5MUGykUr3FXl54VrlSaQG9CRUivCLdGvYndfQy3AiNbhAJUlT3FBJ2beG5TIpW7IDIYDyzKSSORgr1tRBxk/rw7G3Z5HIHpu8h678ezGjUTyRNPHlzg==

復号例
_encrypted_str=jSS9OzYlOpPDR9+lLWObL3QaIV5ehbk6PO6MTIoUoYZ5E1r8xuu6a/MWn/IpD6hK8D5D3sAjNT9fJ4YK7E8wAeqiyN57CKDLaG5Rh3fjuETrkO0ZHUhnthOXp1YDYSRHRx8e/vWKM+Fisi6q8Ym7iTX2KUoPhcQ1iH+hypmncnrGUbRo3XB8/34hO6HRHF5WEItT8m2pVFnI8bvi+HYxNtX7Dh0BzNvW4KT5MUGykUr3FXl54VrlSaQG9CRUivCLdGvYndfQy3AiNbhAJUlT3FBJ2beG5TIpW7IDIYDyzKSSORgr1tRBxk/rw7G3Z5HIHpu8h678ezGjUTyRNPHlzg==

echo $_encrypted_str | base64 -D | openssl rsautl -decrypt -inkey ~/.ssh/id_rsa 

復号結果
message

script

rsaencrypt ()
{
(

MESSAGE="$1"
SSH_RSA_PUB_KEY="$2"

function modpow ()
{
(
_b=$1
_e=$2
_m=$3

_result=1

export BC_LINE_LENGTH="100000000000"

_result=$(cat <<EOF | bc
b=$_b
e=$_e
m=$_m

ret = 1 
for  ( i=0 ; i < e ; i ++  ) {
  ret = ( ( ret * b ) % m )
}

ret
EOF)

echo $_result
)
}

function rsa_pkcs_padding_for_string ()
{
  
# 鍵のサイズになるまでパディングする。
# EB = 00 || BT || PS || 00 || D . 
# | 0 | 2 | Nonzero random bytes | 0 |      Message        |
echo "" >&2
echo "##### padding pkcs#1" >&2


#16進文字列で返すことにする
#_file_data="$1"
_string="$1"
_key_length="$2"

#_bytes_of_file=$(bytes_of_file $_file_data)
_bytes_of_data=${#_string}
_bytes_of_key_length=$(echo "scale=0;$_key_length / 8" | bc )

decimal_to_hex 0
decimal_to_hex 2

#ランダムでパディング。0にはならないように。
_i=0
_padding_size=$( expr $_bytes_of_key_length - $_bytes_of_data - 3)
echo "_bytes_of_data: $_bytes_of_data" >&2
echo "_bytes_of_key_length: $_bytes_of_key_length" >&2
echo "_padding_size: $_padding_size" >&2

while test $_i -lt $_padding_size
do
_rand=$(expr $(od -vAn -N4 -tu4 < /dev/random  ) % 254 + 1)
decimal_to_hex $_rand
_i=$(expr $_i + 1)
#echo $_i >&2
done


decimal_to_hex 0
#echo "$_string"
printf "$_string" | od -An -tx1 | tr -d "\n " | dd conv=ucase 2>/dev/null
}
  
function hex_to_decimal ()
{
(
_hex=$1
export BC_LINE_LENGTH="100000000000"
echo "obase=10;ibase=16;$_hex" | bc
)
}

function decimal_to_hex ()
{
(
_num="$1"
#_hex=$(printf '%x' $_num)
export BC_LINE_LENGTH="100000000000"
_hex=$(echo "obase=16;ibase=10;$_num" | bc)
_hex_length=${#_hex}

if test $(expr $_hex_length % 2 ) -eq 1
then
_hex_length=$(expr $_hex_length + 1)
_hex="0$_hex"
fi

printf $_hex |  dd conv=ucase 2>/dev/null
)
}

function decimal_to_bin()
{
(
_num="$1"
_hex=$( decimal_to_hex $_num )
#_bytes=$(expr ${#_hex} / 2 )
#_pos=1
#while test $_pos -le ${#_hex}
#do
#printf "%b" "\x$(printf $_hex | cut -b${_pos}-$(expr $_pos + 1) )"
#_pos=$(expr $_pos + 2)
#done
_bytes=$(expr ${#_hex} / 2 )
#echo "bytes:"$_bytes >&2
print_bin_padded_hex $(hex_string_padding $_hex)

)
}

function hex_string_padding ()
{
(
hex="$1"
length_of_hex=${#hex}
if test $(expr $length_of_hex % 2 ) -eq 0; then printf "$hex"; else printf "0$hex"; fi
)
}

function print_bin_padded_hex ()
{
( 
hex_padded="$1"
for byte in $(echo $hex_padded | fold -w2 -b); do printf "%b" "\x$byte"; done
)
}

function parse_ssh_rsa_pub_key ()
{
(
SSH_RSA_PUB_KEY="$@"


function num_from_bin_file()
{
  (
  file_bin="$1"
  head="$2"
  size="$3"
  hex=$(cat $file_bin | dd bs=1 skip=$head count=$size | od -An -tx1 | tr -d "\n "| dd conv=ucase)
  export BC_LINE_LENGTH="100000000000"
  echo "obase=10;ibase=16;$hex" | bc
  ) 2>/dev/null
}
file_bin=$(mktemp -t convrsa)
echo $SSH_RSA_PUB_KEY | cut -d" " -f2 | base64 -D >>$file_bin

head=0

length=$(num_from_bin_file $file_bin $head 4)
head=$(expr 4  + $head)
value_string=$(cat $file_bin | dd bs=1 skip=$head count=$length 2>/dev/null)
head=$(expr $length + $head)

echo "type:"
echo "length : $length bytes"
echo $value_string

length=$(num_from_bin_file $file_bin $head 4)
head=$(expr 4  + $head)
value_num=$(num_from_bin_file $file_bin $head $length)
head=$(expr $length + $head)

echo "e:"
echo "length : $length bytes"
echo $value_num

length=$(num_from_bin_file $file_bin $head 4)
head=$(expr 4  + $head)
value_num=$(num_from_bin_file $file_bin $head $length)
head=$(expr $length + $head)

echo "n:"
echo "length : $length bytes"
echo $value_num

rm $file_bin
)
}


function rsa_encrypt ()
{
#(
_str="$1"
_e="$2"
_n="$3"
_file_data=$(mktemp -t rsa_encrypt)
  export BC_LINE_LENGTH="100000000000"
_hex_n=$(echo "obase=16;ibase=10;$_n" | bc)
_num_pub_key_bit_length=$(expr ${#_hex_n} "*" 4 )


echo $_str >&2
echo $_num_pub_key_bit_length >&2

#_hex_padded_data=$(rsa_pkcs_padding_for_string "$_str" $_num_pub_key_bit_length | od -An -tx1 | tr -d "\n "| dd conv=ucase )
_hex_padded_data=$(rsa_pkcs_padding_for_string "$_str" $_num_pub_key_bit_length)


echo $_hex_padded_data >&2
_num_padded_data=$(hex_to_decimal $_hex_padded_data)

echo "" >&2
echo "##### calc modpow" >&2
echo "modpow $_num_padded_data $_e $_n " >&2


_num_encrypted_data=$( modpow $_num_padded_data $_e $_n)

echo "###### result modpow" >&2
echo $_num_encrypted_data >&2

decimal_to_bin $_num_encrypted_data
#decimal_to_hex $_num_encrypted_data

#)
}


echo "### start" >&2
echo >&2
echo "##### parse ssh-rsa public key"  >&2
NUM_E=$(parse_ssh_rsa_pub_key "$SSH_RSA_PUB_KEY" | grep -A2 -e "^e:$"| tail -n1)
NUM_N=$(parse_ssh_rsa_pub_key "$SSH_RSA_PUB_KEY" | grep -A2 -e "^n:$"| tail -n1)
echo "e:$NUM_E" >&2
echo "n:$NUM_N" >&2

echo >&2
echo "##### rsa encrypt " >&2
echo "message: $MESSAGE">&2


_encrypted=$(rsa_encrypt $MESSAGE $NUM_E $NUM_N | base64 )

echo "encrypted:$_encrypted" >&2
echo $_encrypted
)
}

#rsaencrypt "message" "ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQDNckEuuAeiPesx99s/ivWoXQGdJIMKRl0I0HiSLMCdK/dUrXy5ycyy51cEtv0t/AGQCkAxqiYBCWiVhLV/1qpZuONL9UT8cTa4TO749lFVaucxLNN7nvUtbtA4InKqRjsjqK27vCzyWxiMVIMX0jNpD0rPCwkTK2Ja6knCRN7kA2c3UyNmX4IoQ0xqT0vaUNuxtOe9SkmT3DLizDMbYByzJWVgotbZfOu1QbbClpLt/TbDd5l3fcGNsRzT8Cnd8zdvXk5ZsiUDKKhynvA4Tt/LN9LjZgxTyoEYJewYzf51E8gH057A9zXguBTTAiHMgD8xgeGzh4AVEEFJ1ZO6oCft Guest@shigeta-no-MacBook-Pro.local"


テスト

#注意　このスクリプトは暗号解読時に秘密鍵へのアクセスがあります。opensslへの引数。
# ~/.ssh/id_rsa ~/.ssh/id_rsa.pub が対である前提。

(

#_file_tmp=$(mktemp -t convrsa)

(
_encrypted_str=$(rsaencrypt "test" "$(cat ~/.ssh/id_rsa.pub)" )


_decryptedstr=$(echo $_encrypted_str | base64 -D | openssl rsautl -decrypt -inkey ~/.ssh/id_rsa ||{
echo "error" 
exit 1 
})
echo $_decryptedstr

if test "$_decryptedstr" != "test"
then 
echo error
exit 1
fi
) && echo success 

) 


実験scripts

べき乗余

function modpow ()
{
(
_b=$1
_e=$2
_m=$3

_result=1

export BC_LINE_LENGTH="100000000000"
while test $_e -gt 0
do
 echo "$_e" >&2
_result=$(echo "( $_result * $_b ) % $_m " | bc )
_e=$(expr $_e - 1 )


done

echo $_result
)
}


test べき乗余
(
test $(modpow 5 3 3) -eq $(echo " (5 ^ 3) % 3" | bc) || error modpow 5 3 3
test $(modpow 100 2 3) -eq $(echo " (100 ^ 2) % 3" | bc) || error modpow 100 2 3
)
さてここで問題が。すごく遅いです。なので、bcにほとんどの処理を任せるように作り直してみます。
#bc で mod pow
function modpow ()
{
(
_b=$1
_e=$2
_m=$3

_result=1

export BC_LINE_LENGTH="100000000000"

_result=$(cat <<EOF | bc
b=$_b
e=$_e
m=$_m

ret = 1 
for  ( i=0 ; i < e ; i ++  ) {
  ret = ( ( ret * b ) % m )
}

ret
EOF)

echo $_result
)
}

なんとか５分以内に終わりそうです。勉強でも暗号化に１時間かかってたらやる気が出ません。
#メモ化してみたいね
function modpow ()
{
(
_b=$1
_e=$2
_m=$3

_result=1

export BC_LINE_LENGTH="100000000000"

_result=$(cat <<EOF | bc
b=$_b
e=$_e
m=$_m


ret = 1 
for  ( i=0 ; i < e ; i ++  ) {
  if (table[b] != 0) {
    ret=table[b]
  } else {
    ret=( ( ret * b ) % m )
  }
}

ret


EOF)

echo $_result
)
}


##### pkcs#1 padding
```bash
# 鍵のサイズになるまでパディングする。
# EB = 00 || BT || PS || 00 || D . 
# | 0 | 2 | Nonzero random bytes | 0 |      Message        |

function rsa_pkcs_padding_for_string ()
{
# 鍵のサイズになるまでパディングする。
# EB = 00 || BT || PS || 00 || D . 
# | 0 | 2 | Nonzero random bytes | 0 |      Message        |
  
  
#16進文字列で返すことにする
#_file_data="$1"
_string="$1"
_key_length="$2"

#_bytes_of_file=$(bytes_of_file $_file_data)
_bytes_of_data=${#_string}
_bytes_of_key_length=$(echo "scale=0;$_key_length / 8" | bc )

decimal_to_hex 0
decimal_to_hex 2

#ランダムでパディング。0にはならないように。
_i=0
_padding_size=$( expr $_bytes_of_key_length - $_bytes_of_data - 3)
echo "_bytes_of_data: $_bytes_of_data" >&2
echo "_bytes_of_key_length: $_bytes_of_key_length" >&2
echo "_padding_size: $_padding_size" >&2

while test $_i -lt $_padding_size
do
_rand=$(expr $(od -vAn -N4 -tu4 < /dev/random  ) % 254 + 1)
decimal_to_hex $_rand
_i=$(expr $_i + 1)
#echo $_i >&2
done


decimal_to_hex 0
#echo "$_string"
printf "$_string" | od -An -tx1 | tr -d "\n " | dd conv=ucase 2>/dev/null
}


function bytes_of_file ()
{
echo $(wc -c "$1" | tr -s " ") | cut -f1 -d " "
}

function hex_to_decimal ()
{
(
_hex=$1
export BC_LINE_LENGTH="100000000000"
echo "obase=10;ibase=16;$_hex" | bc
)
}

function decimal_to_hex ()
{
(
_num="$1"
#_hex=$(printf '%x' $_num)
export BC_LINE_LENGTH="100000000000"
_hex=$(echo "obase=16;ibase=10;$_num" | bc)
_hex_length=${#_hex}

if test $(expr $_hex_length % 2 ) -eq 1
then
_hex_length=$(expr $_hex_length + 1)
_hex="0$_hex"
fi

printf $_hex |  dd conv=ucase 2>/dev/null
)
}

function decimal_to_bin()
{
(
_num="$1"
_hex=$( decimal_to_hex $_num )
#_bytes=$(expr ${#_hex} / 2 )
#_pos=1
#while test $_pos -le ${#_hex}
#do
#printf "%b" "\x$(printf $_hex | cut -b${_pos}-$(expr $_pos + 1) )"
#_pos=$(expr $_pos + 2)
#done
_bytes=$(expr ${#_hex} / 2 )
#echo "bytes:"$_bytes >&2
print_bin_padded_hex $(hex_string_padding $_hex)

)
}

function hex_string_padding ()
{
(
hex="$1"
length_of_hex=${#hex}
if test $(expr $length_of_hex % 2 ) -eq 0; then printf "$hex"; else printf "0$hex"; fi
)
}

function print_bin_padded_hex ()
{
( 
hex_padded="$1"
for byte in $(echo $hex_padded | fold -w2 -b); do printf "%b" "\x$byte"; done
)
}


ssh-rsa分解

(
SSH_RSA_PUB_KEY="ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQDNckEuuAeiPesx99s/ivWoXQGdJIMKRl0I0HiSLMCdK/dUrXy5ycyy51cEtv0t/AGQCkAxqiYBCWiVhLV/1qpZuONL9UT8cTa4TO749lFVaucxLNN7nvUtbtA4InKqRjsjqK27vCzyWxiMVIMX0jNpD0rPCwkTK2Ja6knCRN7kA2c3UyNmX4IoQ0xqT0vaUNuxtOe9SkmT3DLizDMbYByzJWVgotbZfOu1QbbClpLt/TbDd5l3fcGNsRzT8Cnd8zdvXk5ZsiUDKKhynvA4Tt/LN9LjZgxTyoEYJewYzf51E8gH057A9zXguBTTAiHMgD8xgeGzh4AVEEFJ1ZO6oCft Guest@shigeta-no-MacBook-Pro.local"

function num_from_bin_file()
{
  (
  file_bin="$1"
  head="$2"
  size="$3"
  hex=$(cat $file_bin | dd bs=1 skip=$head count=$size | od -An -tx1 | tr -d "\n "| dd conv=ucase)
  export BC_LINE_LENGTH="100000000000"
  echo "obase=10;ibase=16;$hex" | bc
  ) 2>/dev/null
}
file_bin=$(mktemp -t convrsa)
echo $SSH_RSA_PUB_KEY | cut -d" " -f2 | base64 -D >>$file_bin

head=0

length=$(num_from_bin_file $file_bin $head 4)
head=$(expr 4  + $head)
value_string=$(cat $file_bin | dd bs=1 skip=$head count=$length 2>/dev/null)
head=$(expr $length + $head)

echo "type:"
echo "length : $length bytes"
echo $value_string

length=$(num_from_bin_file $file_bin $head 4)
head=$(expr 4  + $head)
value_num=$(num_from_bin_file $file_bin $head $length)
head=$(expr $length + $head)

echo "e:"
echo "length : $length bytes"
echo $value_num

length=$(num_from_bin_file $file_bin $head 4)
head=$(expr 4  + $head)
value_num=$(num_from_bin_file $file_bin $head $length)
head=$(expr $length + $head)

echo "n:"
echo "length : $length bytes"
echo $value_num
)
暗号化

文字列というより数字をいじっているって感じを出すために１０進数で行く
暗号化する文字列は公開鍵に対して十分短いこと。（別に説明）
#NUM_E=65537
#NUM_N=25935193570591516257910889133015789328715925439541891051310696926598176978965975464614768218048998241722422908206393388363262305195190208720830465570517281304173758664432492974389526033210765772492126485781538585561098545712440529542896864873396444756790065961239554775178462284826504394726083048739449278253787507089325526913567919160484732480506884740050266792114116693534320642521418787476705163205685743149359114257055623949169788413731431431453286977093738826953224469995257093908253062667619136556291964870501482533773385926608901486753729003068552970434418266166694970574858706796295804349144542750503558195181
NUM_E=35
NUM_N=24234252096874441807135898456420917325823918964936243272759984400219706145554397942317537561139702481961523698917643330222257667797385443399955665615983789876278622355412914461082947830772686710692498515388817049521208090699841154133345563327123181959386026146265989072174094572040871089500982084754436618421520017884817412294742784092374564250245334804337616632365543295434087468069665449463993310260825052048240025829007377173512109294755056749261677976599337196484166968106961554664336265720887918536531083889828745288183836432301167199892700414704147561483848055668958512145687098919256933524989248841129488065027
function rsa_encrypt ()
{
#(
_str="$1"
_e="$2"
_n="$3"
_file_data=$(mktemp -t rsa_encrypt)
  export BC_LINE_LENGTH="100000000000"
_hex_n=$(echo "obase=16;ibase=10;$_n" | bc)
_num_pub_key_bit_length=$(expr ${#_hex_n} "*" 4 )


echo $_str >&2
echo $_num_pub_key_bit_length >&2

#_hex_padded_data=$(rsa_pkcs_padding_for_string "$_str" $_num_pub_key_bit_length | od -An -tx1 | tr -d "\n "| dd conv=ucase )
_hex_padded_data=$(rsa_pkcs_padding_for_string "$_str" $_num_pub_key_bit_length)


echo $_hex_padded_data >&2
_num_padded_data=$(hex_to_decimal $_hex_padded_data)
echo "run command  modpow $_num_padded_data $_e $_n " >&2


_num_encrypted_data=$( modpow $_num_padded_data $_e $_n)

echo $_num_encrypted_data >&2

decimal_to_bin $_num_encrypted_data
#decimal_to_hex $_num_encrypted_data

#)
}


_encrypted=$(rsa_encrypt "message" $NUM_E $NUM_N | base64 )

echo $_encrypted | base64 -D | openssl rsautl -decrypt -inkey ~/.ssh/id_rsa


#if (!$pubkey) return false;
#    $data = this.pkcs1pad2($data,($pubkey.modulus.bitLength()+7)>>3);
#    if(!$data) return false;
#    $data = $data.modPowInt($pubkey.encryptionExponent, $pubkey.modulus);
#    if(!$data) return false;
#    $data = $data.toString(16);
#    $data = Hex.decode($data);
#    return Base64.encode($data);

参考資料


javascriptによるrsa暗号
rsa pksc#1 パディング
べき剰余