Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

Anonymous
Anonymous asked in 電腦與網際網路程式設計 · 2 decades ago

密碼學裡,有一種加密法叫做 Hill cipher

輸入檔: pe.in /輸出檔: pe.out

在密碼學裡,有一種加密法叫做 Hill cipher, 方法如下:

假定我們要加密的文字都是由大寫字母 (A-Z)、小寫字母 (a-z) 及底線 (_) 共 53 種字元組成。我們先把這些字元這樣編號:_ 是 0, A 是 1, B 是 2, ..., Z 是 26, a 是 27, ..., z 是 52。如果我們要加密 "National_Problem_Solving_Contest" 這一段文字,我們先設定 block size 為 4,以 4 個字元為一組把原文切成很多個 block:"Nati", "onal", "_Pro", ..., "test"。另外,我們還有一組加密公式:

y1 = (3 x1 5 x2 2 x3 0 x4) mod 53

y2 = (1 x1 -7 x2 6 x3 4 x4) mod 53

y3 = (-5 x1 -8 x2 0 x3 0 x4) mod 53

y4 = (-1 x1 -1 x2 -1 x3 -1 x4) mod 53

我們不妨把這組加密公式稱做「母體 (Matrix)」,其中 mod 53 代表除以 53 取餘數 (介於 0 到 52 之間),例如 61 mod 53 = 8, 而 -61 mod 53 = 45。

接下來,我們開始對每一個 block 來加密。以 "Nati" 為例,我們先按照上面的字元編號轉成一組數字 (14, 27, 46, 35), 然後把 (x1, x2, x3, x4) = (14, 27, 46, 35) 代入「母體」之中,得到 (y1, y2, y3, y4) = (4, 29, 32, 37),再把這一串數字轉成文字,就變成 "Dcfk"。用這個方法把每一個 block 都加密完成之後,就變成 "DcfkFVEMIyeERygWR_GHbPJCrNcVLRzr"。你也可以改變上面的各項的係數以產生不同的「母體」來加密。不過值得注意的是,不是所有的「母體」都能用來加密,因為有些母體加密出來的文件有可能解不出原來的內容。

當然,整個 Hill cipher 最重要的東西,就是所謂的「母體」了。如果不知道「母體」的內容,你就很難破解出原文來。但是這套加密法有個破綻,就是只要你拿到足夠數量的原文以及加密後的結果,你就可以分析出這個密碼系統的「母體」,進而破解 Hill cipher。身為情報部門幹員的你,偶然間攔截到了敵國的機密文件,以及這份文件加密後的文字,因此你必須寫一個程式來破解這個加密系統,以便當敵國日後再用這套系統加密傳送機密資料時,能夠立即破解出原文。

輸入檔說明:

輸入檔的第一列包含一個數字 T, 代表輸入檔裡面有多少套 Hill cipher 系統等著你破解。在每一套系統裡的第一列是一個數字 n (1 ≤ n ≤ 100),代表 block size。接下來有三個部分:第一個部分是你得到的機密文件內容,第二部份是這個機密文件加密過後的結果,第三部份是你要破解的其他加密過後的資料。每一個部份都是由上述 53 種字元所組成。這三個部份字元數都是 n 的倍數,且不會超過 65536 個字元。一整套系統的格式如下:

4block size

=====以一列 "=====" (5 個等號) 開始第一部份。

National_Problem_機密文件內容,可能會被分成很多列。

Solving_Contest

=====以一列 "=====" 開始第二部份。

DcfkFVEMIyeERy加密過的文件內容,也可能被分成很多列。

gWR_GHbPJCrNcVLRzr

=====以一列 "=====" 開始第三部份。

RZDCrYapMEDiDpAk你要破解的加密文件,可能被分成很多列。

=====以一列 "=====" 結束整套系統。

輸出檔說明:

針對輸入檔的每一套系統,輸出你破解出來的原文。請你把原文輸出成一列,不要隨便換行。因此你的輸出檔應該會有 T 列。如果因為攔截到的資訊不足,或是資料不正確 (說不定這是敵國故意放出來擾亂的訊息),導致無法分析出唯一一組「母體」,請你輸出 "Unable to crack the Matrix"。

範例輸入:

1

4

=====

National_Problem_

Solving_Contest

=====

DcfkFVEMIyeERy

gWR_GHbPJCrNcVLRzr

=====

RZDCrYapMEDiDpAk

=====

範例輸出:

Crack_the_Matrix

Update:

這不是功課好嗎 =.=

有這麼難的功課喔 這是 2004年網際網路程式設計全國大賽 的題目

http://contest.cc.ntu.edu.tw/npsc2004/

我是真得看不懂 也不會寫...

Update 2:

豆豆龍(小黑)

我沒參加 ~.~ 我朋友要去比...

跑來問我 可是我也不會 ><”

因為我也滿想知道怎麼解的

所以就來問網上的人

結果沒得到有用的回答

還被罵到一點人格都沒有 @@”

Update 3:

當然是動了腦經才來問 可是連題目我都看不懂了 怎麼可能貼出程式碼 

總不會要我貼個

Private Sub Form_Load()

End Sub

來給人家笑吧~!

Update 4:

當然會希望有程式碼 對我來說 不但可以了解題意 

還可以知道一些 老師 或 書上 所 沒教 沒寫 或 解釋不明 的 程式碼 

像 Liu-Liu 之前幫我解的問題 就用了一些 我從來沒看過的程式碼

還跟我講了 一個說明檔 從他那裡學到了很多東西 之後 很多題目 用他給的方法

真的解的很快 而且程式碼也很短 受益很多

Update 5:

最想了解的是 每個人不同的解題技巧 

一個題目的解法 一定不可能只有一種 過程才是精華 當然你不給程式碼 給個想法 意見

對我來說 這也很重要 也是精華 因為這也是一個過程

Update 6:

這個問題 我的老師也 投降... 

他跟我說 另請高明 @@”

你不是我的老師?! 孔子不是說

任何人都可以當任何人的老師嗎?

比我利害就是我的老師阿~!

證明題:

我看不懂 你看的懂 還可以解釋出來

你比我利害 所以你是我的老師

老師不會跟學生有利益關西吧~! ^^”

5 Answers

Rating
  • Anonymous
    2 decades ago
    Favorite Answer

    功課請自己來

    找槍手請錢先拿來

    2005-11-09 11:05:54 補充:

    本來就該自己動腦經去想怎麼解,而不是依靠別人來解給你看,要別人解給你看的話,何不去問老師更快?老師還會覺得你這小孩不錯,有學習的意願,更樂意教你。我們又不是你的老師,解決問題又沒拿薪水,上班解你們的問題基本上被老闆發現還會被扣薪。更何況連自己『試做』都懶得去做,直接來找答案,當然該被唸。問問題的誠意都沒有,誰還願意要回答?下次問問題前,先寫過一遍,寫不通時,把自己的程式碼放上來問,錯在哪裡這才是問問題的方式,而這樣的方式,我們也都樂意回答。你要的大致上的作法去這邊參考吧http://tw.knowledge.yahoo.com/question/?qid=140511...

    2005-11-11 09:08:44 補充:

    老師哪裡跟學生沒利益關係?

    呵呵~

    學生家長付錢給學校,學校付錢給找來的老師要他指導你

    這不是利益嗎?呵呵~去逼迫壓榨你的老師吧

    作法就麻煩你照著連結過去吧...

  • 1 decade ago

    我覺得不要對想找答案的人太苛求,因為就是想解決又無法解決才想上來求助於大家,教學相長不是很好嗎?如果有問題,不能問同學,不能問老師,問大家又不肯教,一味的罵人家不寫答案,只會問人家要答案,那這就好了,大家都不要交作業,等死好了,反正又沒人幫忙,還會被罵,這就是台灣人跟外國人的差別,沒有同理心。

  • Anonymous
    2 decades ago

    我也正在想,

    P.S:你是不是要參加今年的npsc???

  • 2 decades ago

    問題長是還好,該讓人知道的線索都有出現,也能明白需求是什麼,長? 那又如何?

    不過這看起來超像作業的題目,就算有了答案也不想回答。

  • How do you think about the answers? You can sign in to vote the answer.
  • 文彥
    Lv 5
    2 decades ago

    那麼長的問題應該沒人會想要回答吧

Still have questions? Get your answers by asking now.