猜數字遊戲

Posted by tjwei on 星期日, 6月 18, 2000 with No comments

猜數字遊戲 (1)

猜數字的遊戲有很多種,一種相當有名的,稱為幾 A 幾 B,典型的規則是,兩個人玩,雙方各準備一組四位數的數字,不讓對方知道。雙方輪流猜對方的數字,先猜中對方數字的人贏。當對方猜了一個數字時,你要告訴 對方一些線索,你要告訴他他的答案中,有多少個數字猜中,但放的位置不對,有多少個位置放了正確的數字,,比方說你的答案是4162,他猜的是2156, 那 1就是位置正確,數字也正確, 6 和 2 他有講到,但位置不對,就是猜到但位置不正確。回答的方式使用一種簡稱,位置正確的數字稱為 A,猜到但位置不正確的稱為 B,以剛才的例子來說,就要回答 1A2B,這也就是幾 A 幾 B 的名稱由來。

這個遊戲似乎是由猜顏色的遊戲演變而來的,只不過把要猜的四個位置換成了顏色,回答的方式改為使用幾黑幾白來回答,也有商品問世,有 個上面有許多洞塑膠盒子,可以讓你把有顏色的塑膠釘子插到上面,方便進行遊戲。好處是可以重複使用,不用浪費紙張,但顯然不比以紙筆進行遊戲方便。即使猜 的是顏色,仍然可以算是廣義的猜數字遊戲,因為本質上其實沒有什麼不同。這個遊戲簡單的調整一些參數,比方說四位數改成六位數、十進位改成十二進位、數字 可以重複或者不能重複、第一位可以是零、只能是零等等,就能有許多變形。這類遊戲是不是有什麼最佳的解法?以及多少次能解出來,我這裡沒有資料,但以典型 的規則來說,這個遊戲使用最簡單的方法:「第一次隨便亂猜,以後每次,依據對手給的提示,猜一個有可能的答案。」就已經有不錯的效果了。
也因此為這個方法如此簡單,當一些 BBS 提供猜數字遊戲時,我們可以使用自動程序來取代人力,賺取 BBS 金幣。

猜數字遊戲 (2)

雖然說靠著固定的演算法來猜數字,理論上是相當有效的,但自限於數學化的前提,往往會忽略了數學往往會簡化現實。方法的假設前提,忽略了數字本 身是不同的,面對於人類出題者, 5678 出現的機會絕對和 1479 是不同的,同樣的,當你面對的是人類答題者的話,如果你出的題目是1234,有很大的機會第一次就被猜中。即使雙方利用本質上完全相同的方法,如果能善用 對手的慣性,贏面的確很大。
那電腦出題又如何?細心的程式設計的確能讓出題及答題的參數非常的隨機,讓所有的取巧方式毫無著力點,也有可能設計出人工智慧能夠觀 察出對手的行為模式予以痛擊,不過一旦開始利用對手之前的行為模式作為往後判斷的依據,那你的的判斷也出現了模式,這時鹿死誰手還未可知。
但一般來說,不值得為這樣一個小東西來寫一大堆程式,比方說我的自動猜數字程式來說,該開始的版本,甚至一開始都猜同一個數字,每次 猜的方式都一樣,所以出題者聰明的話,可以選擇一個數字,讓程式每次都必須花費最大的回數才能猜中。解決的方法,就是使用亂數。但是,電腦的亂數基本上就 是一個亂數表,當你程式執行之後,要求亂數的時後,系統會依序把亂數給你,也就是說,程式執行後,每次的亂數序列都一樣,所以一般來說,程式設計者會在程 式開始時,設定一個特別的亂數表種子,設定依據通常都是時間的函數,絕大多數人都是直接把現在時間拿來當亂數表的種子。這樣,程式每次執行時,都會給出不 同的亂數了。
BBS 上的出題的方式還是有很多可能,奸詐一點的BBS 甚至可以不用出題,因為他不需先公布答案。但是使用亂數是最簡單的方式,即使如此,還是有許多可能,光是電腦上的亂數表就有好幾種了,選擇種子的方式也有 很多,就算是這些不管,我們要如何產生一個四個不同的數字呢?我的猜數字程式使用的方式是,先產生一個 0123 到 9876 之間的隨意亂數,然後檢查他是不是每一位都不同,如果不是的話,重新產生一個亂數,直到成功為止。這只是一種方式,你也可以產生一個介於 1 到 10*9*8*7之間的亂數 n,然後尋找第 n 個四個位數都不同的數字。

猜數字遊戲 (3)

BBS 上使用的不見得是這兩者,在猜數字遊戲風行的時候,我曾在某站上發現,每次上站之後,每次的答案,都是固定的一個序列,簡單的說,那個BBS 上沒有設定亂數種子,因此,光靠手動輸入,馬上都能一回合猜中,迅速成為暴發戶。但是,對於我們猜數字遊戲的主力不良牛來說,就沒有如此容易了。觀察我的 猜數字程式的紀錄之後,發現了一個有趣的現象,不良牛的預設數字並不是完全的亂數,他的第一位數和第二位數必定奇偶相反,後面幾位也有高於平均值的比例奇 偶相間。觀察到如此明顯的行為模式之後,馬上把這個模式利用進去,大膽的叫猜數字程式只猜前兩位奇偶相反的數字,加入這個規則之後,猜的回合數從平均五回 合多,變成平均三回合多,賺錢的效率明顯增加了。但是為什麼會造成這種現象呢?原來有一種舊的亂數表是奇偶相間的,對於亂數品質要求不高的情形下,還算堪 用,但在現在的狀況下,卻造成了有趣的現象。
但又為什麼後面幾位沒有必然奇偶相間呢?猜測的結果是不良牛產生四位數不同的數字,使用的方法應該是:先隨機從 0~9中選出一個數字,當作第一位,然後,在從 0 到 9 中隨機取出一個數字,如果和第一位不同,就當作第二位數字,如果和第一位一樣,那再隨機取一個數字,直到和第一位不同為止。第三,四位也用和第二位類似的 方式,從 0 到 9 中隨機取出一個數字,比較和前面幾位有沒有重複,有的話,重新挑一個數字,直到和前面幾位不同。在這個方法中,第二位和第一位其實不用作比較,因為一奇一 偶,一定不同,但我們猜不良牛的作者一定忽略了這點。依照這個方式,我們可以算出第三位和第二位奇偶相間的機率,也可以算出第四位和第三位奇偶相間的機 率,拿來和之間記錄的數字來統計,發現結果是吻合的。

猜數字遊戲 (4)

由於和統計的結果吻合,所以對於不良牛的出題方式就有了完整模型,剩下來的,就是要確定亂數種子,先用一般的方法猜個兩三次,得到前兩三次的答 案,然後這邊就開始利嘗試亂數種子,套進我們猜測的出題模型,看看會不會得到和面所得的答案一樣。這些嘗試都進行得很順利,而且得到不良牛使用的亂數種子 就是直接使用時間這個結論。
就這樣,又把之前的平均三次多猜中,降到平均一次猜中,一個不能再好的結果。
這個猜數字的最佳成果所帶來的收益成果,也不過就是那了一大堆不良牛金幣,除了送人,也不知道能有什麼用。最後,該站的出題程式也改了,給獎金額也做了限制。
也有其它能得到比較實際利益的猜數字遊戲,那就是猜密碼了。
和幾 A 幾 B 一樣,密碼的選擇,也是可以很隨機的,面對著設計良好的密碼檢查系統,猜出密碼的唯一的選擇,就只有花費天文數字時間的暴力搜尋了。很幸運的,猜密碼也是 一種廣義的猜數字遊戲,我們面對的出題者同樣也常常是有行為模式的人類,或者有行為模式的電腦程式。
比方說,對於一個常常連上的主機而言,即使是對於密碼安全相當重視的人,也不會選擇一個非常困難輸入的密碼。一般而言,情況甚至更 好,大多數人在實務上會把方便性的優先權放在安全性的前面。太長又複雜的密碼,不小心忘了怎麼辦,又很難打,常常會打錯。所以,絕大多數複雜而安全的密碼 就被物競人擇掉了。
為了解決人們討厭輸入複雜密碼的困擾,許多的軟體開始貼心的幫使用者記住密碼。可惜的是,這樣並不會帶給那些複雜難記得密碼任何福 利,反而更加打壓他們的生存。為什麼?軟體幫我們記住了複雜的密碼,那複雜密碼的難打性和難記性的困擾不就解決了嗎?為什麼反而更容易淘汰?原因很簡單, 由於軟體幫使用者記住了密碼,使用者不需要常常使用這個密碼,反而很容易就忘記了密碼,不要說複雜的密碼了,就算是簡單的密碼,久了不用,也很容易就忘 了。一般來說,這不會造成困擾,反正軟體幫你記住了,你記得住、記不住也就不重要了。但也許有一天,你換了新電腦了,更新軟體了,或者中毒了,也許有次有 急事使用別人的電腦,連上主機時,突然發現腦筋一片空白,完全忘了當初設定的密碼是什麼?猜了幾次,終於放棄了。從此以後,你發誓再也不用自己記不住的密 碼了,並且把他抄起來,貼在螢幕旁,而且所有的帳號都使用相同密碼。
所以,有了自動記憶密碼的軟體,只會讓密碼變的更簡單、更單純,也很少有人會沒事去改密碼。
所以,一般原則下,猜密碼的空間只要鎖定在「記得住」和「方便打」的交集就可以了。
可惜即使如此,我們還是很難像有些電視影集上演的,潛入別人的辦公室,打開電腦,試著猜了兩次密碼都拒絕存取,皺了皺眉頭,看到辦公桌上放了一張父女合照,靈機一動,打了那個女兒的名字,歡迎畫面就出來了。

猜數字遊戲 (5)

如果真的有要在 login: 和password: 的提示符號下,親手猜測密碼的話,login名稱 guest, password 空白的會有一點成功率。如果有已經知道一些帳號名稱,比方說 NT 的輸入密碼方塊會顯示上一個login 的帳號名稱,可以試著在密碼的欄位輸入帳號名稱,比方說帳號名稱如果是 weijr,可以是著猜猜看密碼是不是也是 weijr,如果不行,還可以試試看 weijr1, weijr2, weijr0,如果都不行,再猜一下 1234 試試看。
如果都不成功,不要喪氣,這是非常正常的,如果人在主機旁邊,可以看看桌子上,螢幕旁,或者旁邊牆上有沒有剛好貼有密碼,這個可能性在公開的環境中還不小。如果面對的是 Unix 主機,下面有一些可以嘗試的(帳號:密碼)組合:
StoogR:
    wank:wank
    root:D13HH[
    root:D13hh[
    root:wh00t!
    gamez:lrkr0x
    rewt:satori
    hax0r:
    friday:
也許已經有別人先偷偷裝好後門了。
如果都還不行,你還是可以隨意的猜測一些,猜越多,中獎率一定就越高,不過越多的嘗試,會顯現出越多的惡意。
用手猜密碼成功率高嗎?不高,不過我真的有猜中的經驗。
一般來說,沒有人會徒手去猜密碼的。
也可以用和幾 A 幾 B 的方法,靠者電腦連線程式自動化的去猜,但是,這就和徒手猜的一樣,過多的嘗試,會顯得具有侵略性,搞不好就會被抓起來。
所以一個小結論就是,除非是真的很差的密碼,沒有其它資訊輔助的狀況下,此路不通。
在此,思考的方向就要轉向機器是如何判斷密碼是正確的?顯然電腦的硬碟上面一定存有密碼的資料,用來和使用者的輸入比對,用來確定密碼 是否正確。但是,這樣的話,機器的管理者不就可以知道所有使用者的密碼了嗎?如果使用者剛好在其它的地方也使用了相同的密碼,那心懷不軌的管理員就可以堂 而皇之的借用這個使用者的帳號了。比方說好了,你在藍盒的密碼,如果剛好和你在椰林的密碼一樣,那藍盒的站長會不會用這個密碼幫你處理你在椰林的郵件?
的確有些站台他們會知道你的密碼,所以,他們才能提供一些特別的服務,比方說當你忘了密碼,他們可以幫你記起來,或者像是剛才說的幫你偷偷處理你在椰林的郵件。
藍盒以及絕大多數的 BBS 無法提供這種服務。
但這又是怎麼辦到的?如果說藍盒不知道使用者的密碼,又怎麼能檢查使用者的密碼是不是正確的?

猜數字遊戲 (6)

既然藍盒不知道你的密碼,又怎麼能檢查你輸入的密碼是不是正確的?
解決的方法是這樣的,藍盒上面不會存有你的密碼,但是我們存有一份經過編碼處理過的你的密碼。我們可以把編碼處理看成一個函數,F,你 的密碼如果是X,我們這裡就存有F(X),比方說你的密碼 X 是 hello,那 F(X) 就會出來 Gjy3.U5xOfA 這樣一組沒有人看的懂得編碼,這樣,不管是藍盒的站長還是誰,只能看到 Gjy3.U5xOfA,看不到你的密碼 hello 了。
要比較使用者輸入 Y 和密碼 X 是不是一樣,只要比較F(Y) 和 F(X) 是不是一樣就行了。
我的數學系 b81同學們看到這個地方,一定會看到一點問題,沒有錯, F(Y) 和 F(X) 相同,不能保證 X 和 Y 相同,比方說另一個密碼 world 經過 F 處理後,也會成為 Gjy3.U5xOfA。所以呢,F 需要一點特殊要求,就是不同的密碼,經過 F 處理之後,也要得到不同的編碼,數學上說的就是 1 to 1 。實務上的要求沒有那麼嚴格,但至少,重複率要很低,非常的低。
另外一個問題是,BBS 的站長當然可以看BBS 的程式碼,也知道 F 的編碼過程,難道不能把 F 反解回來嗎?數學上來說,的確存在一個 F 的右反函數 G,使得 F(G(X))=X ,所以站長「只要能」找到這個 G,就可以偷得使用者的密碼了,但困難的就在於找到這個反解法。
已經知道編碼的方法,倒著回去,不就可以得到反編碼法了嗎?我曾經被這個問題困擾了一陣子,然後一步一步的把密碼編碼法拆解,然後看 到了不可逆的部分,終於相信了。其實不需要這樣子才能瞭解。這裡的不可逆,和數學的不可逆有點不一樣,事實上,前面已經說了,像 F 這樣的函數,的確存在足夠好的反函數,數學意義上它是可逆的。
什麼是這裡的不可逆,舉個例子比較快,比方說我們讓F(X) = 第 X 個質數的平方根小數點一位到十位。求出 n=F(X) 相當容易,只要拿出夠好的計算機,計算第 X 個質數,把小數點拿出來就可以了。但相反的,如果是已經知道了 n=F(X),想知道 X 是多少,只得慢慢的找了。所以這裡的不可逆,只是很難找的意思,難到只能一個一個慢慢去試。
最難也只能這樣了,你沒有辦法阻止我一個一個去試。
但是,你怎麼知道只能一個一個去找,也許有捷徑?不用太驚訝,這是一類很古老的問題。還記得中學學的一元二次方程式嗎?或者多元一次聯立方程式?方程式就是我們的 F,解方程式就是尋找看看有沒有快速得到 G 的方法。
對幾千年前的人來說,F(X)=5X^3+6X^2+7X 已經夠好了。

猜數字遊戲 (7)

除了不可逆的編碼外,另外還是有一些軟體會使用可逆的編碼法,比方說,Windows 撥號網路的密碼記憶,為了不讓人輕易讀到它幫你記憶的密碼,所以加以編碼,但編碼又一定要可逆,因為視窗要幫你輸出密碼。
就某方面來說,這樣甚至比用明文記憶更糟。
還是回到前面的不可逆編碼,既然找不到快速的可逆解法,我們至少能慢慢把密碼試出來,雖著編碼方式的不同,試出來的時間當然也不同。比 方說,我們可以在兩天的時間之內,使用個人電腦,試出任何一個由英文字母,阿拉伯數字,標點符號,空白反正就是你鍵盤能夠直接敲出來或者加上 Shift鍵能敲出來的那些東西組成的密碼。反之,一般 Unix 的 crypt編碼,需要的時間就久多了,不是一兩年能夠出來的。
雖然,必須要慢慢去試,但是,我們還是有有趣的猜數字遊戲可以玩。
比方說台大計中好了,會要求學生、老師和職員,在申請帳號時,填寫一個預設密碼。當年我申請時,發現一堆人把申請單放在一個籃子內,我 根本就不用猜,就可以看到許多人的密碼了。這當然不夠有趣,有趣的是,計中限定你設定的密碼,必須前兩位是英文字母,後四位是數字,比方說, ab1234,那前兩位的英文字母可不可以用大寫?就我瞭解是可以的,但多數人都有疑惑,在對於大小寫沒有特別喜好的情況下,大多數人,在詢問職員和只用 小寫之間,會選擇後者。
這樣,大大的減少我們的搜索範圍和花費的時間。
26*26*10000 ,看起來是一個大數字,即使用很普通的個人電腦,也不需要花費幾小時就能試完。當然前提是,要先有編碼過的密碼表。一般的情形下,計中不會讓你看這個表,但在某些情況下,是可以拿到這個表的。也可以使用一些不太難的技巧,主動拿到這個表。
問題是解一個密碼,花費的時間不多,但我們需要猜很多密碼的時候,怎麼辦?

猜數字遊戲 (8)

面對一萬多個帳號,即使是只要試 aa0000 到 zz9999 之間的可能,也要花費不少時間。還好,這些數字之間,不是平等的, ab1234 永遠比 kt2493 吃香一點,但問題是,哪些數字是吃香的?我們知道,生日永遠是密碼選擇的主流,所以第一個數字是 0 的機率不小,第三個數字也常常是 0,1,2 ,如果你手上剛好有一份學號和生日的對照表,也許可以先試一下。但是,許多人並不是使用自己的生日,而是親朋好友的。況且,生日也不見得是平鋪直述的使 用,所以期望不要太高。另外,1234,5678, 7777這種數字,也比較吃香。與其花腦筋空想,不如使用統計的方式,把有人用過的密碼來做一統計。光是哪一位、哪一個數字、哪一個字母比較常用,已經有 不錯的效果了。
總之,雖然使用者隨時可以改密碼,但由於前面所說的,既然電腦都幫你記住密碼了,誰還會記得去改密碼?另外一方面,使用者很可能會誤會說,密碼一定要前兩位字母、後四位數字。所以,光是用這個方法,可以解出的密碼超過七成,甚至有九成以上的解碼率。
解出密碼有什麼用處呢?簡單的說,除了得到大家沒有良好的密碼習慣這個結論,並且感嘆一下外,似乎沒有什麼用處。這也不算是什麼用處,因為不需要解出密碼也知道結論。
還有什麼用處呢?連上別人的帳號,可以看別人的信,使用硬碟空間,不是什麼有意思的事情。但是,幫別人查成績,倒是蠻有趣的。

猜數字遊戲 (9)

說到查成績,其中也有一個猜數字遊戲。
查成績遊戲的第一版,雖然也需要輸入密碼,但由於當時作者技術上的限制,所以在輸入密碼後,查成績系統會利用學號,產生一個特別的數 字,利用學號和那個數字,就能查到成績了。問題就在於,數字是經由黑箱產生的,我們能看到數字,能看到學號,但我們不知道數字怎麼產生的。不過呢,一個很 明顯的現象是,班上的同學似乎產生的數字差不多,研究室內的許多人,都知道一些密碼,一個一個拿來試試,證實了這個結論,而且,觀察到了,某個學號是最小 值,然後向兩側上升,這樣的函數,該不會是一個開口向上的拋物線啊?
多試了幾個學號,證實了這個猜測,然後又試了一些別的系的學號,把整個黑盒子都解出來。
因此,在數學系的網路上,有了一個特別版的查成績服務,讓那些沒有在計中申請帳號的同學,也能查到自己的成績。
只讓在計中有帳號的同學能查成績,實在是一種不公平。
當然了,這招現在已經行不通了,不過呢,手上一堆帳號和密碼對照表,還是可以幫別人查成績的。
光查查成績似乎不夠有趣,那幫別人領錢又如何?

猜數字遊戲 (0)

**本篇文章受密碼保護,請輸入密碼後繼續閱讀: ********
密碼錯誤!
請再試一次: *********
密碼錯誤!
請再試一次: *********
....
Categories: ,