4

私は BigNumbers ( http://oss.digirati.com.br/luabignum/bn/index.htm ) の助けを借りて、Lua で RSA 暗号化スクリプトに取り組んできました。ただし、ごく一部のケースでは、暗号化された元のメッセージが元のメッセージに復号化されておらず、その理由がわかりません。これは非常に大きな数 (たとえば 1.08e107) を扱うことに注意してください。私が書いたコード全体を以下に示しますが、これが何をすべきかの内訳です。

print(rsa_getkey())

p: 83
q: 23
n: 1909
e: 19
d: 1899
phi: 1804

上記は、公開鍵が[n、e]で表され、秘密鍵が[n、d]で表されるキー値を設定します。これは、次のコードで実現されます。

function rsa_getkey()
  rsa_e = 0
  local primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 57, 71, 73, 79, 83, 89, 97}

  math.randomseed = os.time()

  rsa_p = primes[math.random(5,#primes)]
  rsa_q = rsa_p

  while rsa_q == rsa_p do
      math.randomseed = os.time()
      rsa_q = primes[math.random(5,#primes)]
  end

  rsa_n = rsa_p*rsa_q
  rsa_phi = (rsa_p-1)*(rsa_q-1)

  while rsa_e == 0 do
      local prime = primes[math.random(1,10)]
      if rsa_phi%prime > 0 then
          rsa_e = prime
      end
  end

  for i = 2, rsa_phi/2 do
      if ((i*rsa_phi)+1)%rsa_e == 0 then
          rsa_d = ((i*rsa_phi)+1)/rsa_e
          break
      end
  end
  return "p: ",rsa_p,"\nq: ",rsa_q,"\nn: ",rsa_n,"\ne: ",rsa_e,"\nd: ",rsa_d,"\nphi: ",rsa_phi,"\n"
end

キーが決定されたら、メッセージを暗号化できます。プレーン テキスト ("Hello world") を数値システムに変換するために、100% 完全ではないが、最も基本的な形式で機能する関数を作成しました。

print(rsa_plaintext("Hello_world"))

1740474750625850534739

次の関数は、そのメッセージが決定される方法です。

function rsa_plaintext(x)
  local alphanum = {A=10, B=11, C=12, D=13, E=14, F=15, G=16, H=17, I=18, J=19, K=20, L=21, M=22, N=23, O=24, P=25, Q=26, R=27, S=28, T=29, U=30, V=31, W=32, X=33, Y=34, Z=35, a=36, b=37, c=38, d=39, e=40, f=41, g=42, h=43, i=44, j=45, k=46, l=47, m=48, n=49, o=50, p=51, q=52, r=53, s=54, t=55, u=56, v=57, w=58, x=59, y=60, z=61, _=62}
      rsa_cipher = ""
  for i = 1, #x do
      local s = x:sub(i,i)
      rsa_cipher = rsa_cipher .. alphanum[s]
  end
  return rsa_cipher
end

最後に、これをより管理しやすくするために、セグメントに分割する必要があります。時間とコードを節約するために、実際の暗号化と、平文から数値形式への変換、そして暗号化を組み合わせましたが、デバッグ目的で復号化を追加しました。このコードは、メッセージに 0 を付加して、各グループが 4 桁になるようにします。これが私の問題の出番です。Msg と Decrypted は同一である必要があります。

print(rsa_group("Hello world"))

Msg: 1740
Encrypted: 1560
Decrypted: 1740

Msg: 4747
Encrypted: 795
Decrypted: 929

Msg: 5062
Encrypted: 1659
Decrypted: 1244

Msg: 5850
Encrypted: 441
Decrypted: 123

Msg: 5347
Encrypted: 429
Decrypted: 1529

Msg: 3900
Encrypted: 1244
Decrypted: 82

これは、次の 2 つの関数で行われます。

function rsa_group(str)
  local cipher = {}
  local str = rsa_plaintext(str:gsub(" ","_"))
  local len = #str
  local fillin = ""
  if len%4 ~= 0 then
      fillin = string.rep(0,(4-len%4))
  end
  str = str..fillin
  for i = 1, #str, 4 do
      local s,e = i, i+3
      local part = str:sub(s,e)
      print(rsa_encrypt(part))
  end
end

function rsa_encrypt(msg)
  bnrsa_e = BigNum.new(rsa_e)
  bnrsa_n = BigNum.new(rsa_n)
  bnmsg = BigNum.new(msg)
  result = 0
  quo = BigNum.new()
  rsa_c = BigNum.new()
  result = BigNum.pow(bnmsg, bnrsa_e)
  BigNum.div(result, bnrsa_n, quo, rsa_c)

  bnrsa_c = BigNum.new(rsa_c)
  bnrsa_d = BigNum.new(rsa_d)
  result = 0
  quo = BigNum.new()
  rsa_C = BigNum.new()
  result = BigNum.pow(bnrsa_c, bnrsa_d)
  BigNum.div(result, bnrsa_n, quo, rsa_C)

  return "Msg:",msg,"\nEncrypted:",rsa_c,"\nDecrypted:",rsa_C,"\n"
end

さて、これは長い質問であり、問​​題自体には多くの要素があることはわかっています。私は自分の問題がどこにあるのかを理解する方法に途方に暮れています。足りないものはありますか？新鮮な目のセットが私の解決策かもしれません。

4

1 に答える 1

2

よく調べてみると、メッセージは2 つの素数の積よりも小さくMなければならないようです。上記のテスト ケースでは、最初のメッセージを除くすべてのメッセージが より大きいため、適切に復号化できませんでした。 nn = 1909

たとえば、Mを超えたところを考えてみましょうn = 1909。

Msg: 1910
Encrypted: 1
Decrypted: 1

Msg: 1911
Encrypted: 1222
Decrypted: 2

Msg: 1912
Encrypted: 1179
Decrypted: 3

現実世界の例でnは、もちろんかなり大きいため、この問題が発生する可能性ははるかに低くなります。

于 2013-11-05T08:45:45.750 に答える