暗夜間諜的密令

暗夜間諜的密令

撰文/Dennis E. Shasha|譯者/翁秉仁
轉載自《科學人》2002年12月第10期

過去大家認為,數論是一個詭秘的數學領域,專門研究質數的奇異性質,如今它卻成為現代密碼學的基礎。在當今電子商務交易中廣泛使用的「瑞維斯特–希米爾–艾德曼公開鑰匙密碼演算法」(RSA),就是依靠兩質數的乘積很難被因數分解的道理(大家相信這是對的,雖然尚未證明)。

兩個很大的質數相乘,正是所謂「單向函數」的例子:在電腦上,兩數相乘只需要幾微秒的時間,運算時間與這些數的二進位表示法長度大致成正比;相反的,如果給定乘積,要反求出原本的兩個質因數,就需要很長的時間,例如解一個512位元的乘積,大概要花上幾小時的時間,位數再多則呈緩慢的指數成長(相對於乘積的位數)。假設這個數有2048位元,以目前檯面上所知的方法,要對它做因數分解差不多是不可能的事情。因此,如果真能找到快速做因數分解的演算法,在產業界甚至軍事諜報上的應用都不可限量。

這帶我們來到本期的謎題。這個問題首先是由麥卡錫(John McCarthy,LISP程式語言與理論人工智慧學的發明者)提出的,1950年代被常常有妙點子的拉賓(Michael Rabin,許多重要電腦算則的發明者)給解決了。這個謎題大致如下:假設你手下有一批間諜準備進入敵境,當他們重返國境時,既要避免我方間諜在邊界被我方邊境警衛射殺,同時又要防範敵方間諜潛入,於是邊境警衛利用口令來驗明正身。雖然我們信任己方間諜,也相信警衛很忠誠,但是卻難保這些警衛晚上在酒吧消磨時不會大嘴巴亂講話。在這樣的考量下,我們應該給警衛什麼樣的口令資訊?我方間諜又應該如何說出口令,才能確保只有他們能通過,其他人卻都不行,而且就算警衛要出去喝兩杯也不會壞了大事呢?前面關於質數的討論就是提示。

參考答案:間謀先找到兩個隨機選取的大質數,然後將兩數的乘積交給邊境警衛。當這個間謀返國時,他就將這兩個質數交給警衛,警衛將它們乘起來,看看是否跟先前的數字相同。即使警衛將這個乘積給別人看,敵方要實際分解出這兩個質因數幾乎不可能 (假設因數分解真的很困難)。

(本文由教育部補助「AI報報─AI科普推廣計畫」取得網路轉載授權)

views