2024年12月24日 星期二

RSA 公鑰加密

前些日子網友 ejsoon 留言討論「質數戰爭」數學遊戲,後來個人提議設計一個仿 RSA 密碼破解遊戲,在進一步討論遊戲設計前,先看看 RSA 是如何運作的。

有甲乙兩人要互傳訊息,為了避免內容被破解,大家約定使用 RSA 公鑰加密,為了簡化問題難度,

Step 1
甲自選 8 私人數字 p,乙自選 9 私人數字 q。

Step 2
兩人公開協調使用,基數 B = 2,時鐘尺度 C = 11。

Step 3
兩人以下列算式計算各自的 PPN (Public-Private Number),並且公告之
PPNp ≡ Bp  mod C  = 2⁸ mod 11 3   及    PPNq ≡ Bq  mod C = 2⁹ mod 11 6

Step 4
甲拿取乙的 PPNq = 6,乙取用甲的 PPNp = 3,再與自己的私人數字混和計算出共同秘密 S
≡ (PPNq)p  mod C = 6⁸ mod 11 = 4
   ≡ (PPNp)q  mod C = 3⁹ mod 11 = 4    兩人的共同秘密數值是相同的


上面是計算 (X^n) mod 11 的結果列表,原本想依此原理設計遊戲,並且提供這個表格給玩家參考,可是透漏了 B = 2,其他玩家可以很容易由此查表得知他人的私人數字,另一問題是當指數運算的底數為 3, 4, 5, 9, 10 將發生重複對應問題,因此我改變想法,想改為另外提供類似數獨表,讓每行每列的數值皆不重複,替代上面的 RSA 表,除了重新製表之外,計算方法也需要調整,因為現在給出基數 B 與時鐘尺度 C,很容易反推算出私人數值 p 和 q,需要花時間想一個新方法應用於桌上遊戲。

5 則留言:

  1. 這個遊戲最基本的得分和輸贏機制並沒有設計好,也就不知道怎麼玩,樂趣何在。


    因此我改變想法,想改為另外提供類似數獨表,讓每行每列的數值皆不重複,替代上面的 RSA 表,除了重新製表之外,計算方法也需要調整


    表格和計算方法更換之前,需要考慮的是,到底還用不用rsa非對稱加密?如果仍然是rsa,那就引發幾個問題,一是要創造一種新的加密方法會不會有點難,二是他人如何破解非對稱加密。

    要保證參與者能闖關,但又不能輕易闖關。因此設計這種遊戲是挺難的。

    回覆刪除

  2. 我的一個想法是,把教育部的4808常用字做成表格,等於每個字都有一個編碼,也可以直接用現成的unicode編碼。

    每個人都有他自己的一套加密方法,比如第一位+3。

    小朋友A往外傳送一個明文信息:「我最喜歡吃的水果」。密文信息:9a59。

    則跟A熟悉的小朋友B可能猜出來是哪個字,之後就知道了A的加密方式。小朋友C雖然不知道A喜歡吃的水果,但是通過對表格中有關水果漢字的觀察,也可能推測出A加密的是哪個字。

    隨後A把他的寶藏放在十個箱子中的其中一個,然後A發出寶藏密碼:83179597961f。

    每個人輪流開箱。B小朋友並沒能從「A最喜歡吃的水果」得到足夠信息,所以B沒有破解,B開了第五箱,是空的。

    C小朋友通過對字表上的水果的排查,推測出A喜歡吃的是「橙6a59」,並推出A的加密方法是第一位加3。則破譯出寶藏密碼是「北5317,斗6597,星661f」,則打開第七箱(因為北斗七星)獲得寶藏。

    最終奪寶數量多者獲勝。

    寶藏密碼不能直接是一個數字,否則玩家們只要逐個排查數字就能知道答案。小朋友需要展開想象,生活中哪些東西跟數字有關。這能培養小朋友對數字的敏銳度,並留意觀察生活中的數字。

    回覆刪除
  3. 因為加密解密核心部分還沒搞定,得分與勝負機制自然放在後面再思考。

    確實我面臨兩難局面,如果使用 RSA 密碼系統,可能就人力是無法破解,也就沒有破解的樂趣,如果改其它方法,確實就是另外設計新密碼系統。

    Unicode 是一個不錯的編碼點子,可惜這樣僅限於中文遊戲 (有數千字),對其它種類拼音文字加密方法要修改。

    回覆刪除
  4. 日本有一種遊戲叫「花牌」,主持人吟誦一句詩,這句詩的下一句寫在某張牌上。參賽雙方要爭搶對的那張牌。這個遊戲只能用日文玩,只有日本人會玩。雖然古詩吟誦原本應該是中華傳統文化。

    詩的上句,未必不是一種「加密」。

    《寶藏密碼》如果只能用中文玩,那就中文吧。雖然我認為它也可以改編成其它語言。我從未想過能發明一款遊戲給西方小朋友玩,目前西方人玩的可比我們中文世界要好玩多了,現在絕大多數桌遊都是西方人的發明。

    需要吐槽的是台灣教育部的4808常用字,裏面有好多字我都不認識,比如「疋」竟然是一個常用字,需要查字典才知道,從未見網路文章上有人用過。

    回覆刪除
  5. 對聯,我不認為是加密,上聯只是線索提示。

    謝謝你的分享,疋對我來說是罕見字,小學教布匹的單位量詞是匹,而且在各類書籍文章,我也沒看過有人寫到這個字,它應該是布商的常用字。

    回覆刪除