CodyNote004：簡單解碼環加密問題

來自專欄 Cody習題7 人贊了文章

馬良，祁彬彬

序言

選擇關鍵詞「Cypher」，Cody搜出不少考查古典解密/加密問題，吃瓜群眾喜聞樂見的Caesar Cypher、Vignere De/Encryption、Solitaire cipher均赫然在列，當然，畢竟cody一定程度上是個編程遊戲，受此限制，題目無論規模還是難度都不大，只能算密碼學演算法的「品嘗試用裝」。不過從MATLAB編程的視角來看，實現代碼同樣需要一系列不同函數組合或操作：比如字元串處理、ASCII碼、數組運算、正則表達式等。由於加/解密的要求橫跨文本和字元串兩塊區域，加上索引定址查找、數值和文本的類型切換，所需函數組合之間的關係更是剪不斷、理還亂。今天準備寫點關於這類代碼的分析，想從問題多種求解方式中，加深對常用MATLAB命令組合應用的理解，並捎帶引出一點點關於動態正則表達式(Dynamic Regular Expression)的討論。

Pro.1201：Simple Decoder Ring

鏈接：https://ww2.mathworks.cn/matlabcentral/cody/problems/1201

【原題】：The stereotypical decoder ring is remembered as a cereal box prize from the 1950s. Kids learned about cryptography by starting with the simple transposition cipher. There were many different rings made. One of the more common had two rings on a common center, each with the letters of the alphabet in order. You would rotate the inner ring relative to the outer to produce a shift of letters, so the cipher was to produce a positive or negative shift of the alphabet, giving a letter by letter code key.

Whether or not it really was in cereal boxes, your job is to produce a MATLAB function that codes a string using the letter shift required. You must keep the case of the output the same as the input.

simpleDecoderRing(I am ready to try it - with punctuation and CAPS!,-3)

is

F xj obxav ql qov fq - tfqe mrkzqrxqflk xka ZXMP!

【解釋】：既然被稱為「解碼環」(decoder ring)，這道密碼題很可能就和字元輪轉規律有關，即：輪轉字母順序，按某種規則調整，得到一段難明其意，實則可逆向還原的字符集合，這是加密過程，反之還可按實例反推規則，尋求解密途徑。Pro.1201則屬於其中最簡單的字元輪轉，即：字元串中每個字母按照某長度值，單純移形換位，創造一段同維加密字元串。

Test

Code Input

1

%%inString1 = I am ready to try it - with punctuation and CAPS!;outString1a = F xj obxav ql qov fq - tfqe mrkzqrxqflk xka ZXMP!;assert(isequal(simpleDecoderRing(inString1,-3),outString1a ));

2

%%inString1 = I am ready to try it - with punctuation and CAPS!;outString1b = L dp uhdgb wr wub lw - zlwk sxqfwxdwlrq dqg FDSV!;assert(isequal(simpleDecoderRing(inString1,3),outString1b ));

3

%%inString2 = Dick Tracy is often associated with decoder rings.;outString2a = Lqks Bzikg qa wnbmv iaawkqibml eqbp lmkwlmz zqvoa.;assert(isequal(simpleDecoderRing(inString2,-18),outString2a ));

4

%%inString2 = Dick Tracy is often associated with decoder rings.;outString2b = Zeyg Pnwyu eo kbpaj wookyewpaz sepd zaykzan nejco.;assert(isequal(simpleDecoderRing(inString2,22),outString2b ));

【分析】：把具有明確語義邏輯的句子，按字元移位加密。例如移位長度為2時：A→C、b→d、y→a，「y」移位成「a」，是因為y字母尾部只有1個z字母，位數不夠，自動輪轉，回到字母序首字元a；同理，移位長度為-3時，A→X、b→y、y→v，即：反序移動。題目設置的障礙中，我感覺有2點值得提一提：

• 字元串中其他標點符號、橫線和空格不發生移位變化，原地不動保留；
• 字元區分大小寫，大寫的變完還是大寫，小寫變換完，也還是小寫。

求解代碼及分析

難點分析：字母移位

首先解決字母怎樣按指定長度移位的問題。例如下面這段字元：

str = Rosamund Pike is a beautiful woman, Id like to be her BF.

不動標點符號，但把每個字元向z(Z)方向移動3位，有沒有辦法？

方法1：字元輪轉的MATLAB「標配答案」：circshift

這是最容易想到的方案，circshift能對字元或者數組進行輪轉，例如：

>> circshift(think twice!,3)ans =ce!think twi>> circshift(1:12,3)ans = 10 11 12 1 2 3 4 5 6 7 8 9>> circshift(1:12,-3)ans = 4 5 6 7 8 9 10 11 12 1 2 3

顯然circshift適用於字元串和數組二者的輪轉。不過似乎不能直接套在前述字元串str上，因為circshift完成的是對字元串的橫向輪轉，而不是字元串內每個單字元的縱向移位。但是這也好辦，別忘記了索引變換功能，只需按照移位長度數值，人為製造字元索引的映射表m，就可以用類似「str(m)」的方式實現移位。

map=[1:64,circshift(65:90,[0,-n]),91:96,circshift(97:122,[0,-n]),123:255]

上述代碼創建了一個輪轉英文字母的映射表，這是從ASCII碼，也就是美國標準信息交換碼中脫胎而來的1×255數組，我們知道每個單字元都在ascii碼錶中唯一對應著數值，常用的有：26個大寫字母A-Z對應ASCII碼值為65-90；小寫字母a-z在ASCII碼錶中對應97-122，空格對應32，數字0-9的碼值為48-57等等，其他回車、退格、換行等等也都有自己獨有的碼值。基本ascii碼共有2^7=128個。在第8位上，允許有後128-1個擴展ASCII碼，因此，ASCII碼共計255個，上述map即利用circshift，重新定義整個Ascii碼錶，注意：map變數只改變了65-90、97-122，也就是大小寫字母的定義，這張map就是尋寶圖，剩下按圖索驥的具體瑣碎事宜則交給MATLAB，例如前向移位數值為3，代碼如下：

>> map=@(n)[1:64,circshift(65:90,[0,-n]),91:96,circshift(97:122,[0,-n]),123:255];>> M=map(3);>> char(M(+str))ans = Urvdpxqg Slnh lv d ehdxwlixo zrpdq, Lg olnh wr eh khu EI.

對了，前面提到circshift適用字元和數組移位，因此不用ASCII碼轉換，直接輸入字元串更乾脆：

function ans = simpleDecoderRing( inString, inShift ) circshift(ABCDEFGHIJKLMNOPQRSTUVWXYZ.,-inShift); [ !"#$%&()*+,-./0123456789:;<=>?@ ans []^_` lower(ans)]; ans(inString);end

注意代碼中的ans和lower(ans)正好是65-90和97-122.

方法2：特殊矩陣gallery

思路類似第一種方法，不同之處是利用MATLAB內置特殊測試矩陣命令gallery完成映射表構造，gallery的重載方式相當靈活，有多達20種以上的不同測試矩陣，後置參數調用』circul』時，所得結果接近於問題要求的形式，代碼：

>> Map=gallery(circul,1:255);>> M=Map(1,:);>> M([65:90,97:122])=Map(253,[65:90,97:122]);>> char(M(+str))ans = Urvdpxqg Slnh lv d ehdxwlixo zrpdq, Lg olnh wr eh khu EI.

這種演算法缺點是生成Map時，形成了所有移位順序的碼值映射表，其大小為255×255。執行效率而言，明顯gallery難說適合，但利用gallery是種提示，即：問題中利用這類命令構造符合要求的特殊矩陣，是簡化代碼非常實用的技巧。

此外，注意到Map構造的是純雙精度類型矩陣，為完成向字元轉換，選擇命令「char」恢復為字元串形式。更進一步地，最後一行代碼裡層輸入變數str字元串前的「+」號不能省略，說明如下：

>> strA=Im a stringstrA = Im a string>> +strAans = 73 39 109 32 97 32 115 116 114 105 110 103

字元要想像數字一樣參與運算，只能換成它的ASCII碼值，+號迫使字元串參與四則運算，這在MATLAB中是自動轉換的，非常方便。

方法3：求余命令

前兩種方案中的circshift和gallery對初學者而言也許相對生僻，實際上用常見函數照樣能解決。下面是一個用求余函數mod實現的方案。首先解釋一下mod和另一個求余命令rem二者功能的重疊和區別之處，比如對正、負數的求余結果：

>> [Modx,Remx]=deal(mod(13,3),rem(13,3))Modx = 1Remx = 1>> [Modx,Remx]=deal(mod(-13,3),rem(-13,3))Modx = 2Remx = -1

對於正數，mod/rem結果相同，但負數則是另一個情況。此外，對0求余結果也不同，mod返回其本身，rem則返回非數NaN，偷懶起見，複製粘貼了幫助中的區別說明。

Differences Between mod and rem

The concept of remainder after division is not uniquely defined, and the two functions mod and rem each compute a different variation. The mod function produces a result that is either zero or has the same sign as the divisor. The rem function produces a result that is either zero or has the same sign as the dividend.

Another difference is the convention when the divisor is zero. The mod function follows the convention that mod(a,0) returns a, whereas the rem function follows the convention that rem(a,0) returns NaN.

Both variants have their uses. For example, in signal processing, the mod function is useful in the context of periodic signals because its output is periodic (with period equal to the divisor).

尤其應當注意最後一段說明：在周期性信號系統內，mod函數就非常有用，因為除數divisor就是mod第2調用參數，這裡所說的輪轉，究其數學本質，其實就是周期性的表現。

所以，字元輪轉相當於mod求余結果，構建小寫字母的移位字元可採用如下代碼：

>> f=@(n)char(97+mod((1:26)+(n-1),26));>> f(3)ans = defghijklmnopqrstuvwxyzabc>> f(-3)ans = xyzabcdefghijklmnopqrstuvw

大寫則需要將「97」改成「65」：

>> Map=@(n)[1:64,65+mod((1:26)+(n-1),26),91:96,97+mod((1:26)+(n-1),26),123:255];>> M=Map(3);>> char(M(+str))ans = Urvdpxqg Slnh lv d ehdxwlixo zrpdq, Lg olnh wr eh khu EI.

大小寫的區分

大小寫的區分是另一個障礙。

關於大小寫區分的問題，其實之前構造字元映射表本身就是一種方案，只是要修改字元的ASCII映射，當移位數量n發生變化，需要重新構造新的映射，這一點能通過匿名函數解決，當然也有其他辦法，比如下面提及的字典式枚舉。

方法1：字典式的枚舉

基本思路是枚舉所有移位字元串，此方法優點是不用管其他特殊字元，重複3次列出字母即可，簡單形象直白，可循環、可判斷；之所以是3次，因為可能存在向前和向後兩種移位形式，缺點是移位數量不能超過26，例如：

function inString = simpleDecoderRing( inString, inShift ) lower = a:z; upper = A:Z; lower_s = circshift(a:z,inShift); upper_s = circshift(A:Z,inShift); for i=1:length(inString) if ismember(inString(i),lower) inString(i) = lower(find(inString(i)==lower_s)); elseif ismember(inString(i),upper) inString(i) = upper(find(inString(i)==upper_s)); end endend

上述代碼分大小寫的基本方式是circshift創建2個字元映射表，通過if判斷本次循環的字元是屬於大寫還是小寫，再用ismember+find查找小寫字母(lower)和大寫字母(upper)的位置。

還有用strfind+新命令contains的做法：

function [ outString ] = simpleDecoderRing( inString, inShift )alpha = abcdefghijklmnopqrstuvwxyz;shiftalpha = circshift(alpha,-inShift);for i=1:length(inString) if contains(alpha,inString(i)) outString(i) = shiftalpha(strfind(alpha,inString(i))); elseif contains(upper(alpha),inString(i)) outString(i) = upper(shiftalpha(strfind(upper(alpha),inString(i)))); else outString(i) = inString(i); endendend

contains是R2016b中，針對string新數據類型的新命令，判定在字元串中是否存在某個子字元串，返回邏輯值，新命令是典型high-level函數，用法簡單好理解，不過功能單一。

字典式構造的改進

上述兩段代碼寫起來有點煩，要做兩次判斷，這個if流程能不能省略呢？

function s = simpleDecoderRing( s, n) ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz; for i=1:numel(s) Ind=find(ans==s(i),2); if ~isempty(Ind) s(i)=ans(Ind(2)+n); end endend

最顯眼的就是開始那段長長的，重複3次的A-Za-z，也可以不這麼寫，這種規律性這麼強的字元串構造，方法真是不要太多，比如repmat+char：

>> repmat([(65:90),(97:122)],3,1);>> char(ans(:))

再比如kron+char：

>> kron(ones(1,3),[(65:90);(97:122)]);>> char(ans(:))

繼續比如repelem+char：

>> repelem([(65:90),(97:122)],1,3);>> char(ans(:))』

方法多種多樣，選一個就行，之所以直接列舉，是因為cody中的字元串size更小，剩下的1個for搞定，不需要分大小寫的情況討論，看見哪個是字母，find可以找到3個相同字母的索引，中間的，移位就行，無需擔心移過頭，因為前後都有相同的一連串字元兜著，也就是連續三個周期存在，只要在n<26就不會出錯。

靈活強悍的正則表達式

連續兩次regexprep

前述第1類方案需要構造映射表，第2類需要逐個字元做循環搜索，並判斷大小寫、哪個是字母哪個是標點符號等等。但搜索、替換字元是正則表達式的拿手好戲，關於正則表達式一言難以盡述，不妨看看我和彬彬的書，裡面有整一章關於正則表達式，從最基本的元字元開始，到動態正則，並伴隨有大量的習題，這裡不再多說。只談一點：MATLAB中的正則尤其強大，原因是MATLAB中非常特別的「動態正則表達式」。所謂動態正則指的是，正則表達式可以和MATLAB中的數組和字元串函數無縫結合，將每次動態搜索得到的文本，用這些比較熟悉的函數轉換成所需內容，並完成替換或者匹配。

以本問題為例，可用正則替換命令regexprep獲得結果：

function ans = simpleDecoderRing( s, n) regexprep(regexprep(s,(?=[A-Z])(w),${char(65+mod($1-65+n,26))}),(?=[a-z])(w),${char(97+mod($0-97+n,26))});end

這段程序最重要是「搜索匹配」和後面的「替換」表達式。

首先搜索匹配：(?=[A-Z])(w)，一共2個括弧，前面括弧代表條件1，「?=」代表只要找到大寫字母就算匹配成功，後面括弧內的「w」意味著匹配到的可以是單獨1個大、小寫字母和數字下劃線，如果匹配一連串字母或數字，可以用「w*」、「w{n}」或「w+」等等。問題中沒有出現下劃線和字母，所以w是OK的。

匹配到字母，下一步是替換，匹配表達式：${char(65+mod($1-65+n,26))}就是所謂的動態正則表達式，用符號「${}」包裹，裡面的char(…)相當於在正則表達式中借用外部函數，即：MATLAB的數組命令處理動態搜索結果字元，本次搜索的結果，用mod函數中的「$1」代替，也就是第1次匹配到的內容，或者說，就是之前搜索式中括弧內的那1個「(w)」，這樣從字元串頭到尾，先搜索匹配大寫，再繼續用一個regexprep匹配小寫。

只用一次regexprep

上述方法連套2個regexprep，有點繁瑣，能不能一次搞定呢？

有兩種方案，第一種是在動態正則上下功夫，寫個走位更風騷的邏輯表達式，放進動態正則式，一次性判斷出大寫和小寫，如下：

function ans = simpleDecoderRing( s, n ) regexprep(s,[a-zA-Z],${char(32*($0>95)+65+mod($0-32*($0>95)-65+n,26))});end

注意搜索表達式無所謂大寫還是小寫，只要搜索到從a到z、從A到Z的任意字母，就算搜索成功。搜索成功，用「$0」代表「當前匹配」成功的字元；後面動態正則式也相應變化：發現其實大寫字母「A」的ASCII碼值是65，小寫字母「a」的碼值則是97，二者相差32，那麼完全可以用：「32*($0>95)+65」構造大寫或者小寫的ASCII碼值，當滿足「($0>95)」的條件時，意味著搜索到小寫字母，邏輯值真(1)，有：32*1+65=97；如果為False(0)，則有：32*0+65=65。這是彬彬提交的方案，很妙！

第2種只需一次regexprep的方案是J.S.Kowontan給出的：

function ans = simpleDecoderRing(s,n) regexprep(s,w,${char(65+mod(upper($0)-65+n,26))},preservecase);end

搜索表達式非常簡單，也沒做判斷，匹配式中壓根不區分大小寫，而是一律用upper($0)給統一成大寫。這就引出問題：最終表達式，即：移位後的字元串，怎麼重新還原最初的大小寫設置？

奧妙就在最後的後置參數preservecase上，看個幫助中的例子：

str = My flowers may bloom in May;expression = M(w+)y;replace = April;newStr = regexprep(str,expression,replace, preservecase)newStr = My flowers april bloom in April

源字元串中出現兩個「may」，一個是「May」，一個是「may」，通過regexprep都被搜索到，並替換匹配成「4月」(April)。匹配結果繼承原有搜索結果首字元大小寫狀態。這是藉助regexprep的後置參數達到的效果，顯然是最方便的方案。

小結

(1).字元串、數組命令及正則表達式間，在MATLAB中沒有嚴格區分，組合和相互交叉並不罕見；

(2).動態正則表達式可用MATLAB的數組和字元串命令對搜索字元進行較為複雜的編輯，相當於對正則搜索的功能實現了「幅值增益」；

(3).Ascii碼值是搭接字元串和數組的橋樑，字元和數值兩種類型藉助Ascii碼無縫轉換銜接，意味著字元串或文本問題，完全可以當做普通雙精度數組的問題處理。

(4).基本的函數命令組合或者後置參數的重載，有很大潛力可挖，例如mod函數被用於描述數據的周期性。

最後匯總不同思路中用到的函數：

推薦閱讀：