看费曼如何开保险箱从猜数字游戏谈起[教育]
看費曼如何開保險箱——從猜數字遊戲談起
作者姓名, 段佳君 張憶婷
指導老師, 曾昭武 老師 一、研究動機
自從看了「別鬧了,費曼先生—科學頑童的
」這本書之後,對於書中提到費曼先生開保險箱速度勝過鎖匠感到非常好奇,究竟他是用什麼
,能夠這麼迅速的猜出正確數字呢,於是我們從猜數字遊戲開始,進一步再嘗試探討密碼學其中的奧妙。
二、研究目的
(一)從原始規則開始,找出每個條件與條件之間的關係,明瞭各數字之間的關
聯性。
(二)利用最原始的方法猜測,統計出所用掉的時間以及次數,看是否能夠利用
最短時間、最少次數之內猜出。
(三)若把數字做分組後再進行猜測,統計出所用掉的時間以及次數,並觀察效
率是否能因此增加。
(四)比較「最原始的方法」與「數字分組的方法」之間的異同、利弊,並把猜
的範圍擴大到五個數字,利用比較好的方法繼續研究。
(五)比較四個數字與五個數字間找到正確數字,和確定數字位置所使用的時
間、花掉的步數之異同。
(六)試著討論猜數字遊戲是否能在六步內猜出。
(七)了解密碼及密碼學的基本意義。
(八)試著探討密碼學與現今高中數學有那些相契合的地方。
三、實驗器材
Word 97,計算機。
四、研究過程或方法
(一)先了解原始規則。
1.數字範圍為0~9十個數字。
2.出題者從0~9中任取4個數字任意排列:數字不可重複:,由玩家猜。
3.若玩家猜的
與題目「數字相同,但位置不同」者,則記為「B」。
4.若玩家猜的答案與題目「數字相同,且位置正確」者,則記為「A」。
5.如此重複猜測,直到猜出答案之條件為4A為止。
(二)從玩過的例子中,任選出一個,並先找出其條件與條件之間的關係以及各數字的關聯性:
次數 數字 提示
1 2537 0A 3B
2 0469 1A0B
3 8253 0A2B
4 1846 0A0B
5 5370 0A2B
6 3729 4A0B
1.由1步到2步時即可知道數字在2,3,4,5,6,7,9,0等八位數字間。
,2步,可知8,1沒有,利用其中一個數字來確定第一步有哪些數字,2.由1
可發現2,5,3有兩個是正確的,即7一定有。 3.由2步有一個數字位置正確,故利用8,1確定沒有來判斷大概是哪一個,可知4,6沒有,0,9中有一個。
4.由3,4條件推導,1中2,5,3取二個,0,9取一個,另加上7做猜測。
5.因2,5,3中有二個是正確的,所以可確定0一定沒有,5,3中有一個,9,2都有。
6.從5,3中取3,把2,7,9擺入,數字位置依據之前所得的條件做適當變換,即可得到答案。
(三)1.由此可發現,當我們在猜答案時,數字擺放的位置要盡量不重複。
2.當全「A」或全「B」的條件愈多,愈快能夠確定正確的位置。
3.每當猜一個答案出來,就要與之前條件相比較,並在猜下一個數字時,符合之前所有的條件,或是利用已知有或沒有的數字,加入判斷其他數字:補足位數:,才不會浪費時間和次數,將效率減低。
(四)由以上可知:
1.利用原始方法所花時間太長。
2.用原始方法的數字排列方式有很多種,若一但假設錯,將會耗掉太多步數。
3.如果條件不夠優越:例如條件一直為2B,1A1B或2A:,因數字排列組戎可能過多,將造戎不易判斷何者為正確答案。 4.若提示間皆有「A」及「B」的條件,將不易排列出正確位置,因其可能性增加許多,如此反而浪費步數。
(五)試著利用數字分組的方式來猜答案,即0~9十個數字做分組。
1.第1步先猜1234。
2.第2步猜5678。
3.第3步根據第1、2步所得的提示,猜測9012或9056。以正確數字個數不為2者之中任取2個與90搭配。若個數相同則選擇「B」較多的做搭配。
4.從第4步開始,根據之前各提示中正確數字的總個數:即「A」加「B」的個數總和:判斷出4個正確數字,但猜的過程中位置可以更換,而不與之前重複,可獲取更多提示,並避免不必要的浪費。
5.判斷正確的位置順序。
我們利用以下兩個例子來說明:
次數 數字 提示 說明
1234 0A2B ,
, 5678 1A1B
5126 2A0B 由,,知90不可能,故先刪除,另,,中各取兩數 ,
, 5147 2A1B 假設51正確,將26換為47
7146 0A2B 假設14正確,7換位置,5換6 ,
,, 1無 , 547有 , 6無 , 2有:為5427 4A0B , 2457重排: , 52位置 , 4位置 7位置
次數 數字 提示 說明
, 1234 0A 1B
7890 1A 2B ,
,, 56不可能,故先刪除,另,中取1位,,中8902 0A 2B , 取3位
7029 0A 2B ,, 7有2無 890取2個 ,
, 0783 2A 2B , 90有1個8有 134取1個
0873 0A 4B , 將78互調 ,
3780 4A 0B ,, 78位置 03位置 ,
(六)由以上可知:
1.用數字分組的方式,可在短時間內
出大概的數字範圍。數字分組的方式是以兩個數字為一組,如此數字的組合將會減少。
ㄅ.一般的猜法:
若1,2,3,4中有兩個正確,則可能性有{12,13,14,23,24,34}。
ㄆ.數字分組的猜法:
若1,2,3,4,將1,2分戎一組,3,4分戎一組,可能性有{13,14,23,24}
再代入下列猜題時答案的排列,若都不合,才有可能為1,2或3,4。
2.一旦分析出數字範圍後,可相對減少猜的時間。 3.若對於數字排列的所有可能結果皆熟練,將可在短時間內求得數字範圍,並且以很少的步數猜出答案,若每一次的答案都極精準且符合所有條件,或利用確定有或沒有的數字排列,確定其他數字,即可獲得最高效益。
4.將數字排列後的可能結果排列排列,如〈
一〉。
(七)比較用原始方法以及數字分組的異同,如〈表二〉。
(八)將數字由4位改戎5位來玩,規則同前面所述。玩法如下:
1.在0~9中任取五個數字。
2.依步驟1的條件,保留正確位數的數字,並由剩下五個數字中取數字與保留的數字搭配補足五位。
3.從第3步開始,根據之前各提示中正確數字的總個數判斷出5個正確數字,但猜的過程中位置可以更換,以獲取更多提示。
4.確定數字後,利用上述條件為「A」或「B」排出正確順序。
次數 數字 提示 說明
12345 0A3B ,
, 34567 0A3B 由,選345做保留,另添加67
93458 0A3B 由,選345保留,更換位置,另加89 ,
, 51634 1A1B 由,改變345順序,加16
, 345不全對,取35,,, 2有6無 7, 85732 3A1B 有,取8
, 75932 2A3B 8換9
, 5732有4個對,732 59732順序 ,不
, 25739 5A0B 合,532 75932順序 ,不合,572 35792
順序 ,不合,為573 25739
次數 數字 提示 說明
, 12345 0A 3B
71236 0A2B 由,選123保留,加67 ,
, 49183 2A1B 設67無 45選4,123選13,890選89
, 28053 2A2B 1換2,4換5
確定67無,,, 8有 23589,23480,12580,, 85013 2A3B 13580四種可能,由13580判斷
58103 2A3B , 設13正確 8為二 , 58103 ,
, 80153 5A0B 8換第一 , 80153
(九)玩5位數字的方法與4位數字時大致相同,都是利用數字分組後排列進行
猜測。
1.猜5位數字較4位不同的是,5位猜測時可在第一步將大致範圍確定。
例如若12345中有2個,則可確定67890有3個。
2.條件為全「A」或全「B」對玩家較有利,因為在數字要排列位置時可以
省略很多的討論步驟。
3.若提示已經為3或4位正確,則把剩下數字的範圍縮到很小,即可迅速
找到正確數字。
(十)比較玩4位數字與5位數字的異同,如〈表三〉。 (十一)若將數字拓展為6位數以上,找正確數字的方法就相當於找不正確的數
字,例如猜6位數字,就相當於找出4位不存在的數字,猜7位就如同3
位,以下類推。且猜測步數將大量耗費在排列順序上,故暫不研究。
(十二)若以0~9十個數字做範圍時,以4位數字最好玩,因為在3次步驟內就
可確定出數字的範圍,而且不需要花太多步數和時間即可猜出,這應也是
原始規則為4位數字的原因。
(十三)討論猜數字遊戲中的5040個答案是否皆可在6步內猜出來〈見附錄〉。
五、實驗結果
(一:在4位數字中,將數字排列後的可能結果討論如下〈表一〉:
1234 0 0 0 0 0 0
5678 2 2 2 3 3 4
9056 2 3 4 2 3
7890 56-1 5690 56-1 56-2 5678
範圍 78-1 78-2 78-1
90-2 90-1 90-1
1234 1 1 1 1 1 1
5678 1 1 2 2 2 3
9056 2 3 1 2 3 1
1234-1 1234-1 1234-1 1234-1 1234-1 1234-1
範圍 78-1 56-1 78-2 56-1 56-2 56-1
90-2 90-2 90-1 78-1 90-1 78-2
90-1
1234 1 2 2 2
5678 3 2 2 2
9056 2 0 1 2
1234-1 1234-2 1234-2 1234-2
範圍 56-2 78-2 56-1 56-2
78-1 78-1
※表中X-Y表示X這些數字中不論位置正確與否,有Y個數字在正確答案
中出現。
(二)使用原始方法以及數字分組的利弊、優缺點如下〈表二〉:
原始方法 數字分組
共費時間 較長 較短
平均總步數 6.6次 6.1次
提示2的方法數 6個 4個
假設錯誤的機率 較高 較低
效率 較低 較高
※因此我們採用數字分組的方法猜測。 (三)比較玩4位數字與5位數字的異同如下〈表三〉:
4位數字 5位數字
初步確定數字範2~3 2 圍:步:
找到正確數字平6.28 6.22 均步數:步:
位置正確平均步6.29 7.22 數:步:
尋找位置所耗步0.01 1.00 數:步:
(四)原始規則規定為4位數字,是因4位數字較不複雜,邏輯上的可能性較少,
所需耗費步數及時間亦較少之故。 (五)討論證明此遊戲的每一個答案是否皆可在六步之內猜測出來。
(六)以分組的方法來猜測,只可相對減少玩家在猜答案時花在邏輯思考上的時
間,並不要求能夠在六步內猜出。
六、討論
(一)為什麼要用分組的方法猜測,
比較能夠用到邏輯的概念,且能在猜的過程中,明瞭每一步之間的關係,
避免做出錯誤的判斷,並且,以這個方法來猜測較容易使人了解玩家在整
個遊戲中的全部思路。
(二)原始方法的缺失在哪裡,
1.因數字排列方式過多,每一個排列都需要分析,故需耗費很多時間。
2.一旦假設錯誤,將造戎步數的浪費。
3.用原始方法猜答案,較雜亂無章,容易將思緒混淆,致使用錯條件,反
而耗費步數、浪費時間。
4.使用原始方法條件紊亂,不易讓人明瞭玩家思路。 (三)如何看出分組的方法比較好,
假設12345五個數字中有2個數字正確,則有可能為
{12,13,14,15,23,24,25,34,35,45},可能性太多,不易找出正確數字。
若用分組的方法,將12345分戎(123),(45)或(12),(345),可在下一步經
由45678或12678的結果,很快的縮小範圍,猜出答案。當我們將數字增
加為六位或七位以上的話由排列數字更可發現分組的優點。
(四)為什麼在猜下一個答案時,數字位置盡量不與之前的位置重複,
因為數字不重複可使獲得的提示增加,在找到正確數字後,排列順序時,
可利用的資訊較多。
(五)在確定正確數字之後,為什麼用條件全為「A」或「B」的提示,會使我們
比較容易猜出正確的位置,
因為條件全為「A」或「B」時,已經可以確知數字必在或必不在哪一位,
因此,可較快刪除不可能的假設。
(六)為何猜5位數字時,確定數字範圍或找出正確數字的次數較4位數字時
少,
0~9十個數字中,猜5位數字時,因為第一步中即可確定數字的大致範圍,
在確定正確數字的時間及步數也會隨之減少。 (七)為何猜5位數字時,猜出答案的步數會較4位數字多,
雖然確定數字較容易,但也因步數少,所得提示較少,在排正確位置時,
需耗費較多的步數來確定位置,因此。猜出答案的步數會較4位多。
(八)試問為何最原始的規則中,以4位數字來進行遊戲,
因為4位數字較不複雜,排列的可能性比較少,而對於以猜數字遊戲作為
娛樂或消遣的大部分人來說,較不會因為猜太多步或時間消耗太多,卻仍
猜不出來,而感到厭煩。較易猜出答案,也比就有戎就感,及再玩的動力,
這樣的遊戲設計即較戎功。
(九)密碼學和猜數字遊戲相似的地方在哪裡?
密碼學主要是在研究保密與解密的各種方法,而猜數字的遊戲目的亦在求
出出題者的謎底,即是一個與其相關的簡單數學遊戲。
七、結論
(一)經由數字的分組,可以有系統的排列出答案,進而能夠很快的找出正確的
數字,排出正確的位置。
(二)在寫每一次的答案時,數字的位置與之前所放的位置盡量不要相同,才不
會造戎條件浪費,增加之後排位置的困難性。 (三)每一步要猜的答案,都要先檢查是否符合之前所有的條件,才不會造戎步
數的浪費。
(四)在排正確數字的可能位置時,要利用條件為「A」或「B」來排列。若有全
「A」或全「B」條件更佳,因其可以確定在該條件中所有正確數字都在或
都不在該位置。
(五)由4位數字擴展到5位數字時,因數字範圍沒有改變:皆為0~9:,但要找
的數字個數改變:4變5:,雖然要找到數字變得較容易,但要排到正確的
位置,卻相對變得較困難。
(六)在玩猜數字遊戲時,通常6~8次內就可猜出來,不過這仍然包含有浪費的
步數在內:猜的時候沒發現的錯誤:,故更精確的次數約在6次左右。
(七)若是利用數字分組的方法來確定答案,可相對減少猜測的時間。
(八)猜數字遊戲看似簡單,其實從第一步到最後一步都是精心設計過的,因此
此遊戲才可以在六步之內猜出正確答案。
八、展望
(一)可把數字範圍擴大到「26個英文字母+10個數字」來猜,猜的數字個數也
可以繼續擴大,但是以數字、字母不重複為原則。 (二)把原始規則改戎數字可重複來玩,可以增進自己猜答案的能力,觀察步驟
是否更複雜。
(三)可再利用電腦做輔助工具,更深入了解密碼學的領域。
(四)探討「密碼學」與現今高中數學相契合的地方,將密碼學帶入高中生的能
力範圍內。
(五)將密碼學與日常生活中做結合。
(六)嘗試自己實際創造出最佳的保密方法。
(七)將0~9想為a0~a9十個座標軸,在十度空間中做幾何範圍的推廣。
九、參考資料
※〈別鬧了,費曼先生—科學頑童的故事〉 頁172~頁199
費曼(Richard P. Feynman)著 吳程遠譯
天下文化出版股份有限公司1993/10/30初版 ※〈近代密碼學及其應用〉 頁1~頁116
賴溪松 韓亮 張真誠著
松崗電腦圖書資料股份有限公司 ※〈大美百科全書 第八本〉 頁100~頁105
光復書局
密碼和密碼學的基本意義
密碼學泛指所有有關研究秘密通訊之學問:包括如何達到秘密通訊及破解秘密:。
密碼學可分為兩個領域:
:一:密碼學:指如何達到資訊的秘密性,為鑑定性的科學:或藝術:。
:二:破密學:泛指如何破解密碼系統,或偽造訊息,使密碼系統誤以為真
的科學:或藝術:。
一個密碼系統的主角有三個人,即發送方、接收方與破密者。在發送方,首先將明文M利用加密金匙K1,將明文加密成密文C=EK1(M)。接著將C利用公眾通道送給接收方,接收方收到密文C後,利用解密器D及解密金匙K2,可將C解密成明文M=DK2(C)=DK2(EK1(M))。破密者並不知道解密金匙K2。但欲利用各種方法得知明文M,或假冒發送方送一偽造訊息,讓接收方誤以為真。
密碼系統為維持其最高安全性,均假設給予破密者最大的知識:即破密者對密碼系統有最深切的了解:。
一密碼系統之安全性必須僅依賴其解密金匙,亦即在一個密碼系統中除解密金匙外,其餘的加,解密器等方法,均假設為破密者完全知道。只有在這個假設下,破密者仍無法破解密碼系統,此系統方有可能被稱為安全。
破密者以其在密碼系統中所獲得的資訊,依其層次可以有下列三種可能的破解方式:
:一:密文攻擊法
:二:已知明文攻擊法
:三:選擇文攻擊法
1.選擇明文攻擊
2.選擇密文攻擊
一般而言,秘密金匙密碼系統中知加密金匙K1,及解密金匙K2,具有下列特性:知道K1即知道K2,反之亦然。在很多情況下,K1等於K2。因此,秘密金匙密碼系統又稱為對稱金匙密碼系統。
一安全的秘密金匙密碼系統,可以達到下列功能:
:一:保護資訊機密。
:二:鑑定發送方之身分。此種鑑定發送方身分之應用,現廣泛使用於銀行
體系中。
:三:確保資訊完整性。
秘密金匙密碼系統具有下列缺點:
:一:收發雙方如何獲得其加密金匙及解密金匙,
:二:金匙的數目太大。
:三:無法達到不可否認性任務。
公開金匙密碼系統,可將加密金匙K1與解密金匙K2分開,使得若知道K1還是無法得知K2。將K1公開,但只有接收方一人知道K2。在此情況下,任何人均可利用K1加密,而只有知道K2的接收方才能解密。或是只有接收方一人才能加密:加密與解密其實都是一種動作:,任何人均能解密。這就是公開金匙密碼系統的主要精神,也是其與秘密金匙密碼系統最大的不同所在。由於加密金匙K1與解密金匙K2不同,因此,此系統又稱為雙金匙密碼系統,或非對稱密碼系統。
公開密碼系統,解決了上述第一個問題,亦即未曾謀面的兩個人,可以透過公共通道,以獲得只有他們兩人才知道的共同金匙。這就是有名的公開金匙分配系統。
安全的公開金匙分配系統,可以達到下列功能:
:一:保護資訊機密。
:二:簡化金匙系統分配及管理問題。
:三:可達到不可否認性功能。
公開金匙密碼系統雖有許多優點,但仍有其缺點存在,即在於加解密運算複雜,且速度緩慢。有人建議利用公開金匙系統達成數位簽署,及解決秘密金匙密碼系統之金匙分配問題。而以秘密金匙密碼系統對明文加解密,達到秘密性功能。此種密碼系統稱為混合型密碼系統。
密碼學所討論的系統,其安全性是最高的評價,一密碼系統之安全性很難用理論證明:事實上證明其為安全很難,但若此系統不安全,則證明其為不安全很容易:。因此,一密碼系統被提出公佈之後,就會有許多人懷疑其安全性,而想要提出破解方式。通常許多系統,在提出後不久,就會被證明為不安全。而密碼系統設計者就會對破解方式進行圍堵與改良,而破密者就會再提出新的破解法。密碼學領域就成長在如此反覆挑戰與改進的環境中。SHANNON在1949年首先對密碼系統的安全性,考慮下列兩個問題:
:一:當破密者有無限制的時間與計算能力,對密文加以分析時,一個密碼
系統最多能有多少安全性呢?
:二:當破密者在有限的時間與計算能力,對密文分析下,一個密碼系統是
否足夠安全呢,
他又定義理論安全及實際安全兩個名詞,所謂理論安全,是指不管破密者截獲多少密文C,並對之加以分析,其結果是與直接猜明文M是一樣的。一密碼系統欲達理論安全,必須加密金匙的長度大於或等於明文的長度。亦即金匙只用一
次,用完即丟,此種系統稱為一次活頁系統。
密碼系統並非一次滿足理論安全才是安全的系統。假設每一密碼系統在給定N位時,均有一破解此一系統的最少工作次數,稱為此系統的工作特徵W(N),原意是指密文攻擊法,但此工作的特徵W(N)可推廣至任何的攻擊方式。W(N)可定義為:所有破解此密碼系統方法中最佳方法所需的最少次數。已知N位密文時,若N為無窮大時,其工作特徵表示為W(?)。若一系統之W(N)大到使得具有有限計算能力及記憶體的破密者,無法在合理的時間內破解此系統,則此系統即可稱為實際安全或計算上安全。
當一密碼系統為安全時,指的是其Wh(N):即歷史工作特徵——破解一密碼所需時間:大到無法在合理時間內被破解。
1976年DIFFIE和HELLMAN[3]提出公開金匙密碼系統的觀念時,他們並未能提出一個真正可以實現的公開金匙密碼系統,只是推測公開金匙密碼系統「可能」存在。他們提出單向函數及單向暗門函數之定義:
單向函數:
一函數F若滿足下列二條件,則F稱為單向函數:
:一:對於所有屬於F之域內的任一X,可以很容易算出F(X)=Y。
:二:對於幾乎所有:ALMOST ALL:對於F之範圍的任一Y,則在計算上
不可能求出X,使得Y=F(X)。
單向暗門函數:
一「可逆」函數若滿足下列二條件,則F稱為單向暗門函數:
:一:對於所有屬於F之域的任一X,可以很容易算出F(X)=Y。
:二:對於幾乎所有屬於F之範圍的任一Y,則在計算上除非獲得暗門,否
-1-1則不可能求出X,使得X=F(Y),F為F之逆函數,但若有一額外資料,
-1則可以很容易求出X=F(Y)。
可知單向函數與單向暗門函數之差異,在於可逆與不可逆。
猜數字遊戲部分證明