看费曼如何开保险箱从猜数字游戏谈起.doc

看费曼如何开保险箱从猜数字游戏谈起.doc 看費曼如何開保險箱——從猜數字遊戲談起 作者姓名, 段佳君 張憶婷 指導老師, 曾昭武 老師 一、研究動機 自從看了「別鬧了,費曼先生—科學頑童的故事」這本書之後,對於書中提到費曼先生開保險箱速度勝過鎖匠感到非常好奇,究竟他是用什麼方法,能夠這麼迅速的猜出正確數字呢,於是我們從猜數字遊戲開始,進一步再嘗試探討密碼學其中的奧妙。 二、研究目的 (一)從原始規則開始,找出每個條件與條件之間的關係,明瞭各數字之間的關 聯性。 (二)利用最原始的方法猜測,統計出所用掉的時間以及次數,看是否能夠利用 最短時間、最少次數之內猜出。 (三)若把數字做分組後再進行猜測,統計出所用掉的時間以及次數,並觀察效 率是否能因此增加。 (四)比較「最原始的方法」與「數字分組的方法」之間的異同、利弊,並把猜 的範圍擴大到五個數字,利用比較好的方法繼續研究。 (五)比較四個數字與五個數字間找到正確數字,和確定數字位置所使用的時 間、花掉的步數之異同。 (六)試著討論猜數字遊戲是否能在六步內猜出。 (七)了解密碼及密碼學的基本意義。 (八)試著探討密碼學與現今高中數學有那些相契合的地方。 三、實驗器材 97,計算機。 四、研究過程或方法 (一)先了解原始規則。 1.數字範圍為0~9十個數字。 2.出題者從0~9中任取4個數字任意排列:數字不可重複:,由玩家猜。 3.若玩家猜的答案與題目「數字相同,但位置不同」者,則記為「B」。 4.若玩家猜的答案與題目「數字相同,且位置正確」者,則記為「A」。 5.如此重複猜測,直到猜出答案之條件為4A為止。 (二)從玩過的例子中,任選出一個,並先找出其條件與條件之間的關係以及各數字的關聯性: 次數 數字 提示 1 2537 0A 3B 2 0469 1A 0B 3 8253 0A 2B 4 1846 0A 0B 5 5370 0A 2B 6 3729 4A 0B 1.由1步到2步時即可知道數字在2,3,4,5,6,7,9,0等八位數字間。 2.由1,2步,可知8,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 0A 2B , 5678 1A 1B , 5126 2A 0B 由,,知90不可能,故先刪除,另,,中各取兩數 , 5147 2A 1B 假設51正確,將26換為47 , 7146 0A 2B 假設14正確,7換位置,5換6 , ,,,1無,,,547有,,,6無,,,2有:為5427 4A 0B , 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 0A 3B , 34567 0A 3B 由,選345做保留,另添加67 , 93458 0A 3B 由,選345保留,更換位置,另加89 , 51634 1A 1B 由,改變345順序,加16 , ,,345不全對,取35,,,,2有6無,7有,85732 3A 1B , 取8 75932 2A 3B 8換9 , ,,5732有4個對,732,59732順序,,不合, 25739 5A 0B 532,75932順序,,不合,572,35792順序,,, 不合,為573,25739 次數 數字 提示 說明 12345 0A 3B , 71236 0A 2B 由,選123保留,加67 , 49183 2A 1B 設67無,45選4,123選13,890選89 , 28053 2A 2B 1換2,4換5 , 確定67無,,,,8有,23589,23480,12580,85013 2A 3B , 13580四種可能,由13580判斷 58103 2A 3B ,,設13正確,8為二,,,58103 , 80153 5A 0B 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)。 可知單向函數與單向暗門函數之差異,在於可逆與不可逆。 猜數字遊戲部分證明 在以下的證明中,均以由左到右的樹狀圖表示。每一組四位數字為該步所猜測的數字,右邊橫線上的數字與字母代表該步獲得的提示。以方框框住的數字代表經過前面的提示為唯一可能的答案,方框框住的提示則代表雖不是唯一可能,但答對的正確答案。由於研究的時間不足,故未能完成所有證明,僅列出較完整部分。