第111章 百萬富翁問題
第111章 百萬富翁問題
RSA加密算法，其利用的主要原理就是大數素因子分解的困難性。
比方說，我們都知道17*13=221，但是當我們看見221這個數字的時候，是否又能夠立馬就看出它等於17×13，那就不一定了。
而如果這兩個數字越大，就越難被破解。
當然，作為專門用來對大數進行因子分解的篩法，就成為了針對這種加密的重要破解方法了。
畢竟篩法本身的原理就是通過不斷的往上乘，而剔除掉那些各種各樣的因子。
所以在針對RSA加密體系中，就有一個叫做一般數域篩的攻擊方式，被公認為最有效破解RSA的加密方法。
當然同樣的問題是，篩法之中存在的奇偶校驗問題，使其在處理那些特別大的數字時，就顯得比較麻煩了，而對於現代RSA加密算法，所使用的就是那些特別大的數字，因此在使用篩法的時候，不可避免的就會在破解的過程中出現極大的偏差。
然而現在……
「對哦……以前用篩法來破解RSA密碼的話，存在較大的困難，畢竟奇偶校驗問題是一個很大的問題。」
梅納德笑哈哈地拍了拍蕭易的肩膀說道：「但是現在嘛，奇偶校驗問題的影響程度都直接被你的分類篩給壓下去了，他們這些搞密碼的都要頭疼咯。」
陶哲軒也笑著說道：「外面的那些人不是總覺得咱搞數學的沒有實際應用的地方嗎？這下好了，咱們直接給他們實際應用一個密碼攻擊。」
見到這兩個數學家幸災樂禍的樣子，旁邊的計算機學家克萊因洛克教授就沒好奇地說道：「有你們這樣去想的麼？要是銀行密碼體系出問題，咱們的社會安定那就也要出問題了。」
「放心啦，咱們都知道，只是有了被破解的風險而已，想要真正實現破解的話肯定還差的遠，畢竟就算是使用篩法去破解，也需要非常多的時間。」陶哲軒倒是沒有被嚇著，擺擺手說道：「不過能讓他們頭疼一下，我們還是挺高興的。」
像他們這些研究純數學的，經常被人問，他們的研究有什麼應用的地方，這也就讓純數學界和其他領域常常發生摩擦。
比如張一唐當年在孿生素質猜想上實現突破後，谷歌就曾經邀請過他去進行演講，但是他拒絕了，因為他表示害怕過去演講之後，被別人問到他的這個成果有什麼用。
同樣的，當年佩雷爾曼在證明了龐加萊猜想後就被各大學校邀請去做演講，對他的證明進行解釋。
結果就有人提問他，他解開了這個方法後有什麼應用的地方，一聽這個問題，佩雷爾曼頓時就勃然大怒，表示怎麼有人問這麼愚蠢的問題，最後受不了，他就直接回俄國了。
總而言之，他們搞純數學的和其他搞應用的，基本上尿不到一個壺裡。
當然，這也就形成了一部分純數學人的一種脾性，如果搞出來的東西越不能用於應用上面，他們就越自得，認為這就是真正的【純粹數學】。
聽見眼前這幾位教授的討論，蕭易無奈地搖搖頭。
這可不是他有意的啊，他當初哪會去想如果自己搞出分類篩，會給密碼學帶來被破解的風險。
「好了，你們也別幸災樂禍，我現在也是想要請教伱們對於這個問題，該怎麼解決，這種涉及到純數學方面的東西，最終也還是要落到你們這些純數學家的頭上。」
克萊因洛克教授說道。
隨後三位數學家也都收拾了一下心情，等待克萊因洛克的解釋。
「唔……想要說明一下何為多方安全算法，咱們首先還是從一個經典問題出發吧。」
「也就是百萬富翁問題，這個問題你們知道嗎？」
陶哲軒點了點頭，他對計算機同樣也有一定的研究，在十幾年前他就曾經搞出來過一個叫做信息獲取指導理論的東西，簡單來說，這是一種數字壓縮成像技術，最終這個技術被廣泛運用於信息領域等等各大方面，充分表現了他在應用數學方面也有著十分強悍的能力。
不過，蕭易和詹姆斯·梅納德就顯得有些為難了。
後者倒是還好，表示自己聽說過這個，「我記得提出這個問題的人是一位圖靈獎得主來著。」
「哈哈，是的。」克萊因洛克點點頭，說道：「說起來，這位圖靈獎獲得者和蕭易一樣，也都是華國人，他的英文名叫做安德魯·姚，中文名好像是叫做姚啟智吧。」
「簡單來說，百萬富翁問題就是，假設有兩位分別叫做愛麗絲和鮑勃的百萬富翁，現在想要比較他們誰更加有錢，但是他們又不想向對方暴露自己到底有多少錢，那麼在這種情況下，他們該如何進行財富上的比較呢？」
說著，克萊因洛克也在黑板上寫下了描述。
【假設愛麗絲和鮑勃兩個人的財產分別為i、j，並且i、j的大小都位於1百萬到10百萬之間，那麼要如何讓對方不知道i或j的具體數字，而實現對i、j大小的比較？】
看著這個問題，陶哲軒倒是知道該怎麼解決，不過梅納德和蕭易就開始思考了起來。
這個問題看上去也挺有意思的。
稍稍過了一會兒，給這兩位留下了一點思考時間，不過克萊因洛克也並沒有想過讓他們現場解答，隨後就開口道：「好了，這個問題咱們可以之後再……」
「等等。」
然而就在這個時候，蕭易開口了，「我想，這個問題也許可以這樣解決。」
隨後他便走到了黑板前，拿起筆開始寫了起來。
【設M是一個所有元素為N-bit非負整數的集合，QN是M到M的置換群。】
「如果我的設計沒有出錯，只要按照接下來的這個協議進行比較，他們就可以在對自身資產保密的情況下完成財富對比。」
「首先，愛麗絲從QN中隨機選擇一個元素Ea作為公鑰，並將其告訴給鮑勃，同時保留Ea的逆Da作為私鑰自己保留。」
「然後，鮑勃隨機選擇一個N-bit的整數x，並利用愛麗絲給的公鑰計算k=Ea(x)……」
隨著蕭易的講述開始，旁邊的三個人就略顯沉默了起來。
他們相互對視一眼，對眼前這一幕有些猝不及防。
特別是詹姆斯·梅納德。
雖然吧，這個問題如果真的要仔細研究一下的話，也不至於難住他，作為一道類似數學建模題而言，它的難度也就那樣。
畢竟，這個問題都已經完全具體化了，從抽象程度來說，它和梅納德研究的那些解析數論上面的問題比較，實在是太小兒科了。
但是，要讓他這麼快就能夠反應過來，並且直接就開始給出方案，那就有些做不到了。
看著蕭易已經寫了半個黑板的東西，梅納德第一次體會到了什麼叫做【降維打擊】。
大概他以前在自己的學生面前展示什麼叫做【頂級數學邏輯思維】的時候，他的學生們也是這樣的感覺吧？
簡直是開了掛了！
克萊因洛克的反應和梅納德也差不多，本來吧，他提出這個問題也沒想過讓他們當場解決出來，剛才留了那麼幾分鐘的時間，也只是讓他們對這個問題稍微熟悉一些。
結果，誰成想，這才幾分鐘過去，這個年輕人就已經開始動筆寫了起來。
原諒他作為一名計算機科學家，數學上面真的不是特別好，至少相比起這些數學家們來說，畢竟有一句話說得好，只有真正數學好的人才能夠一直紮根於純數學，數學不好的人早早地就轉行了。
但是吧，蕭易的這個「數學很好」，未免好得有些超出他想像了。
「第4步，愛麗絲隨機生成一個N/2-bit的素數p，並計算Zu=yu mod p，其中u=1，2，…，10。」
「然後我們保證，所有zu中至少有兩個不相等，否則重新x選擇p計算……」
「愛麗絲將素數p以及【z1，z2，…，zi，zi+1】……重新標記為……」
「鮑勃檢查第zj`，若zj`=x mod p，則說明i大於或等於j，否則i小於j。」
在黑板上寫下了最後一筆，隨後蕭易便回過頭，從頭到尾重新瀏覽一遍，他便滿意地點點頭，然後放下了筆，轉過頭對旁邊的三個人說道。
「這樣，愛麗絲和鮑勃的財富，比較就完成了，而除了雙方財富相等的情況下，他們並沒有向對方暴露出自己的真實財產。」
「克萊因洛克教授，我這個方法應該是可以的，不過具體的程序該怎麼寫，我就不會了。」蕭易謙虛地說道：「我對編程這方面完全不懂。」
然而讓他疑惑的是，眼前的三位教授在此時都稍稍有些沉默。
片刻後，克萊因洛克小聲地問向陶哲軒：「你們數學學的好的人都是這樣的嗎？把我們計算機領域的難題，就當做一個……100以內的加減法給搞定了？」
陶哲軒連連擺手：「呃……這倒不是，但你知道的，這個世界上總會有那麼一些特殊情況，發生一些小概率事件，蕭易就是這樣的小概率事件，你懂的。」
(本章完)
RSA加密算法，其利用的主要原理就是大數素因子分解的困難性。
比方說，我們都知道17*13=221，但是當我們看見221這個數字的時候，是否又能夠立馬就看出它等於17×13，那就不一定了。
而如果這兩個數字越大，就越難被破解。
當然，作為專門用來對大數進行因子分解的篩法，就成為了針對這種加密的重要破解方法了。
畢竟篩法本身的原理就是通過不斷的往上乘，而剔除掉那些各種各樣的因子。
所以在針對RSA加密體系中，就有一個叫做一般數域篩的攻擊方式，被公認為最有效破解RSA的加密方法。
當然同樣的問題是，篩法之中存在的奇偶校驗問題，使其在處理那些特別大的數字時，就顯得比較麻煩了，而對於現代RSA加密算法，所使用的就是那些特別大的數字，因此在使用篩法的時候，不可避免的就會在破解的過程中出現極大的偏差。
然而現在……
「對哦……以前用篩法來破解RSA密碼的話，存在較大的困難，畢竟奇偶校驗問題是一個很大的問題。」
梅納德笑哈哈地拍了拍蕭易的肩膀說道：「但是現在嘛，奇偶校驗問題的影響程度都直接被你的分類篩給壓下去了，他們這些搞密碼的都要頭疼咯。」
陶哲軒也笑著說道：「外面的那些人不是總覺得咱搞數學的沒有實際應用的地方嗎？這下好了，咱們直接給他們實際應用一個密碼攻擊。」
見到這兩個數學家幸災樂禍的樣子，旁邊的計算機學家克萊因洛克教授就沒好奇地說道：「有你們這樣去想的麼？要是銀行密碼體系出問題，咱們的社會安定那就也要出問題了。」
「放心啦，咱們都知道，只是有了被破解的風險而已，想要真正實現破解的話肯定還差的遠，畢竟就算是使用篩法去破解，也需要非常多的時間。」陶哲軒倒是沒有被嚇著，擺擺手說道：「不過能讓他們頭疼一下，我們還是挺高興的。」
像他們這些研究純數學的，經常被人問，他們的研究有什麼應用的地方，這也就讓純數學界和其他領域常常發生摩擦。
比如張一唐當年在孿生素質猜想上實現突破後，谷歌就曾經邀請過他去進行演講，但是他拒絕了，因為他表示害怕過去演講之後，被別人問到他的這個成果有什麼用。
同樣的，當年佩雷爾曼在證明了龐加萊猜想後就被各大學校邀請去做演講，對他的證明進行解釋。
結果就有人提問他，他解開了這個方法後有什麼應用的地方，一聽這個問題，佩雷爾曼頓時就勃然大怒，表示怎麼有人問這麼愚蠢的問題，最後受不了，他就直接回俄國了。
總而言之，他們搞純數學的和其他搞應用的，基本上尿不到一個壺裡。
當然，這也就形成了一部分純數學人的一種脾性，如果搞出來的東西越不能用於應用上面，他們就越自得，認為這就是真正的【純粹數學】。
聽見眼前這幾位教授的討論，蕭易無奈地搖搖頭。
這可不是他有意的啊，他當初哪會去想如果自己搞出分類篩，會給密碼學帶來被破解的風險。
「好了，你們也別幸災樂禍，我現在也是想要請教伱們對於這個問題，該怎麼解決，這種涉及到純數學方面的東西，最終也還是要落到你們這些純數學家的頭上。」
克萊因洛克教授說道。
隨後三位數學家也都收拾了一下心情，等待克萊因洛克的解釋。
「唔……想要說明一下何為多方安全算法，咱們首先還是從一個經典問題出發吧。」
「也就是百萬富翁問題，這個問題你們知道嗎？」
陶哲軒點了點頭，他對計算機同樣也有一定的研究，在十幾年前他就曾經搞出來過一個叫做信息獲取指導理論的東西，簡單來說，這是一種數字壓縮成像技術，最終這個技術被廣泛運用於信息領域等等各大方面，充分表現了他在應用數學方面也有著十分強悍的能力。
不過，蕭易和詹姆斯·梅納德就顯得有些為難了。
後者倒是還好，表示自己聽說過這個，「我記得提出這個問題的人是一位圖靈獎得主來著。」
「哈哈，是的。」克萊因洛克點點頭，說道：「說起來，這位圖靈獎獲得者和蕭易一樣，也都是華國人，他的英文名叫做安德魯·姚，中文名好像是叫做姚啟智吧。」
「簡單來說，百萬富翁問題就是，假設有兩位分別叫做愛麗絲和鮑勃的百萬富翁，現在想要比較他們誰更加有錢，但是他們又不想向對方暴露自己到底有多少錢，那麼在這種情況下，他們該如何進行財富上的比較呢？」
說著，克萊因洛克也在黑板上寫下了描述。
【假設愛麗絲和鮑勃兩個人的財產分別為i、j，並且i、j的大小都位於1百萬到10百萬之間，那麼要如何讓對方不知道i或j的具體數字，而實現對i、j大小的比較？】
看著這個問題，陶哲軒倒是知道該怎麼解決，不過梅納德和蕭易就開始思考了起來。
這個問題看上去也挺有意思的。
稍稍過了一會兒，給這兩位留下了一點思考時間，不過克萊因洛克也並沒有想過讓他們現場解答，隨後就開口道：「好了，這個問題咱們可以之後再……」
「等等。」
然而就在這個時候，蕭易開口了，「我想，這個問題也許可以這樣解決。」
隨後他便走到了黑板前，拿起筆開始寫了起來。
【設M是一個所有元素為N-bit非負整數的集合，QN是M到M的置換群。】
「如果我的設計沒有出錯，只要按照接下來的這個協議進行比較，他們就可以在對自身資產保密的情況下完成財富對比。」
「首先，愛麗絲從QN中隨機選擇一個元素Ea作為公鑰，並將其告訴給鮑勃，同時保留Ea的逆Da作為私鑰自己保留。」
「然後，鮑勃隨機選擇一個N-bit的整數x，並利用愛麗絲給的公鑰計算k=Ea(x)……」
隨著蕭易的講述開始，旁邊的三個人就略顯沉默了起來。
他們相互對視一眼，對眼前這一幕有些猝不及防。
特別是詹姆斯·梅納德。
雖然吧，這個問題如果真的要仔細研究一下的話，也不至於難住他，作為一道類似數學建模題而言，它的難度也就那樣。
畢竟，這個問題都已經完全具體化了，從抽象程度來說，它和梅納德研究的那些解析數論上面的問題比較，實在是太小兒科了。
但是，要讓他這麼快就能夠反應過來，並且直接就開始給出方案，那就有些做不到了。
看著蕭易已經寫了半個黑板的東西，梅納德第一次體會到了什麼叫做【降維打擊】。
大概他以前在自己的學生面前展示什麼叫做【頂級數學邏輯思維】的時候，他的學生們也是這樣的感覺吧？
簡直是開了掛了！
克萊因洛克的反應和梅納德也差不多，本來吧，他提出這個問題也沒想過讓他們當場解決出來，剛才留了那麼幾分鐘的時間，也只是讓他們對這個問題稍微熟悉一些。
結果，誰成想，這才幾分鐘過去，這個年輕人就已經開始動筆寫了起來。
原諒他作為一名計算機科學家，數學上面真的不是特別好，至少相比起這些數學家們來說，畢竟有一句話說得好，只有真正數學好的人才能夠一直紮根於純數學，數學不好的人早早地就轉行了。
但是吧，蕭易的這個「數學很好」，未免好得有些超出他想像了。
「第4步，愛麗絲隨機生成一個N/2-bit的素數p，並計算Zu=yu mod p，其中u=1，2，…，10。」
「然後我們保證，所有zu中至少有兩個不相等，否則重新x選擇p計算……」
「愛麗絲將素數p以及【z1，z2，…，zi，zi+1】……重新標記為……」
「鮑勃檢查第zj`，若zj`=x mod p，則說明i大於或等於j，否則i小於j。」
在黑板上寫下了最後一筆，隨後蕭易便回過頭，從頭到尾重新瀏覽一遍，他便滿意地點點頭，然後放下了筆，轉過頭對旁邊的三個人說道。
「這樣，愛麗絲和鮑勃的財富，比較就完成了，而除了雙方財富相等的情況下，他們並沒有向對方暴露出自己的真實財產。」
「克萊因洛克教授，我這個方法應該是可以的，不過具體的程序該怎麼寫，我就不會了。」蕭易謙虛地說道：「我對編程這方面完全不懂。」
然而讓他疑惑的是，眼前的三位教授在此時都稍稍有些沉默。
片刻後，克萊因洛克小聲地問向陶哲軒：「你們數學學的好的人都是這樣的嗎？把我們計算機領域的難題，就當做一個……100以內的加減法給搞定了？」
陶哲軒連連擺手：「呃……這倒不是，但你知道的，這個世界上總會有那麼一些特殊情況，發生一些小概率事件，蕭易就是這樣的小概率事件，你懂的。」
(本章完)