非對稱加密?到底是什麼鎖可以有兩把鑰匙,用簡單數學解釋給你聽

常聽到非對稱加密是用兩把鑰匙來做,但兩把鑰匙可以用一把來加密一把來解密,到底是什麼鎖可以做到這件事情?這篇文用簡單數學來告訴你這什麼邏輯。

非對稱加密?到底是什麼鎖可以有兩把鑰匙,用簡單數學解釋給你聽

常聽到非對稱加密是用兩把鑰匙來做,但兩把鑰匙可以用一把來加密一把來解密,到底是什麼鎖可以做到這件事情?這篇文用簡單數學來告訴你這什麼邏輯。

非對稱加密用在很多地方,像是 HTTPS 協定、區塊鏈、免密碼登入 SSH等等。原則上你準備一組公私鑰,把公鑰給別人、私鑰留給自己,這樣就可以證明訊息是由你發出去的。

我們先舉個例子好了,我手上有一把私鑰是 91、公鑰是 11。我請你想一個三位數,把這個三位數和公鑰相乘,但只告訴我最後三位數就好,透過私鑰我就可以知道你想的三位數是多少。比方說你腦袋裡想著三位數(原文) 123,你乘以 11(公鑰)得到乘積 1,353 後,給我後面三位數,也就是 353(密文),我得到 353(密文)後再乘以 91(私鑰),最後得到的 32,123,後面三位數就是你心目中原本想的三位數 123(原文)了。

整理一下:

  • 私鑰:91
  • 公鑰:11
  • 密文:353
  • 原文:123

這原理其實很簡單,因為 91 × 11 是 1001,任何數乘上 1001,末三位數都不變。知道原理以後就知道,只要兩個質數乘起來是 X00...001,我就可以拿來做這個運算。

再舉一個例子──現在我算好一個私鑰了,我先不告訴你。而我將原文乘以私鑰後,取後八位數告訴你是:56,770,078,我只告訴你公鑰是 20201,你可以用 20201 乘以 56,770,078 取後八位得到原文是 12345678。

整理一下:

  • 私鑰:(我沒有告訴你)
  • 公鑰:20201
  • 密文:56770078
  • 原文:12345678

你覺得你能算出私鑰是多少嗎?

這題的答案到文末再公布,不過我要再舉一個例子。如果你覺得只能取八位數太少的話,那你用 1199481995446957 × 3334772856269093 = 4000000000000000000000000000001,就有了一個可以存 30 位數的非對稱加密系統。

不過,在實際場域,非對稱加密演算法(如 RSA)不會用乘積那麼簡單的例子,而是用指數和模除的方式來運算。如果想知道 RSA 具體怎麼算的,可以看看 這篇 文章。

雖然公鑰丟出來、密文也丟出來,我就可以解開原文了,但有時候公私鑰加密是拿來驗證你是不是本人。例如你把私鑰留著,公鑰給我,我今天要測試你是不是本人,我可以丟一段測試訊息(assertion)給你,你用私鑰來加密這個訊息(signature),我用公鑰來解開看你的簽名是不是符合我原本的 assertion。

之後會再來舉一些實務上簽名的應用。

最後,上面那題的私鑰是 19801。驗算一下:

$12345678 \times 19801 = 244456770078$
$56770078 \times 20201 = 1146812345678$

參考資料

我們正降低廣告比例以提升閱讀體驗。如果你喜歡這篇文章,不妨按下 Like 按鈕分享到社群,以行動支持我寫更多文章。 或者,你也可以 點此透過 BTC、ETH、USDC 等加密貨幣支持我
分享到: