無法理解凱撒解密步驟-有解無憂

以下代碼將在給定密文和密鑰的情況下解密凱撒加密字串：

#include <iostream>

std::string decrypt(std::string cipher, int key) {
    std::string d = "";
    for(int i=0; i<cipher.length();i  ) {
        d  = ((cipher[i]-65-key 26) %26) 65;
    }
    return d;
}

int main()
{
    std::cout << decrypt("WKLVLVJRRG", 3) << std::endl; // THISISGOOD
    std::cout << decrypt("NBCMCMAIIX", 20) << std::endl; // THISISGOOD
}

我無法理解在這一行計算新字符 ASCII 代碼所執行的操作：

d  = ((cipher[i]-65-key 26) %26) 65;

第一個減法應該移動數字范圍
然后我們將減去密鑰作為凱撒解密的定義
我們加 26 來處理負數 (?)
該模塊將限制輸出，因為 ASCII 數字的范圍是 26 長度
我們通過在末尾添加 65 回到舊范圍

我錯過了什么？

uj5u.com熱心網友回復：

如果我們稍微重新排序運算式，如下所示：

d  = (((cipher[i] - 65)   (26 - key)) % 26)   65;

我們得到一個向左旋轉的公式：cipher[i] key

cipher[i] - 65將 ASCII 范圍A..Z帶入整數范圍 0..25
(cipher[i] - 65 26 - key) % 26旋轉該值左key（減去key模26）
65將范圍 0..25 移回 ASCII范圍A......Z

例如，給定 akey的 2，A變成Y，B變成Z，C變成A，等等。

uj5u.com熱心網友回復：

讓我給你一個關于 Caesar Cipher 的詳細解釋，以便理解這個公式。我還將展示超簡單的代碼示例，以及更高級的一行代碼。

最大的問題是潛在的溢位。所以，我們需要處理它。

然后我們需要了解加密和解密是什么意思。如果加密將所有內容向右移動，解密將再次將其移回左側。

因此，在“def”和 key=1 的情況下，加密后的字串將是“efg”。
并且 key=1 的解密，將它再次向左移動。結果：“定義”

我們可以觀察到我們只需要移動 -1，因此鍵的負數。

所以，基本上加密和解密都可以用同一個程式來完成。我們只需要反轉密鑰。

現在讓我們看看溢位問題。目前我們只從大寫字符開始。字符具有關聯的代碼。例如，在 ASCII 中，字母“A”用 65 編碼，“B”用 66 編碼，以此類推。因為我們不想用這樣的數字進行計算，所以我們將它們歸一化。我們只是從每個字符中減去“A”。然后

'A' - 'A' = 0
'B' - 'A' = 1
'C' - 'A' = 2
'D' - 'A' = 3

你看到了模式。如果我們現在想用密鑰 3 加密字母“C”，我們可以執行以下操作。

'C' - 'A' 3 = 5 然后我們再次添加 'A' 來取回字母，我們將得到 5 'A' = 'F'

這就是全部的魔法。

但是如何處理“Z”之外的溢位。這可以通過簡單的模除法來處理。

讓我們看看'Z' 1。我們做'Z' - 'A' = 25，然后 1 = 26，現在模26 = 0，然后加上'A'將是'A'

等等等等。結果公式為：??(c-'A' key)& 'A'

接下來，否定鍵呢？這也很簡單。假設一個'A'和key=-1

結果將是“Z”。但這與向右移動 25 相同。因此，我們可以簡單地將負鍵轉換為正轉移。簡單的陳述將是：

if (key < 0)  key = (26   (key % 26)) % 26;

然后我們可以用一個簡單的 Lambda 呼叫我們的轉換函式。一種用于加密和解密的功能。只是用一個倒置的鍵。

使用上面的公式，甚至不需要檢查負值。它適用于正值和負值。

所以，key = (26 (key % 26)) % 26;會一直有效。

一些擴展資訊，如果您使用 ASCII 字符表示。請查看任何 ASCII 表。您將看到任何大寫和小寫字符相差 32。或者，如果您查看二進制：

char  dez  bin           char  dez  bin
'A'   65   0100 0001     'a'   97   0110 0001 
'B'   66   0100 0010     'b'   98   0110 0010 
'C'   67   0100 0011     'b'   99   0110 0011 
 . . .

所以，如果你已經知道一個字符是字母，那么大寫和小寫之間的唯一區別就是第 5 位。如果我們想知道，如果char 是小寫，我們可以通過屏蔽這個位來得到。c & 0b0010 0000等于c & 32或c & 0x20。

如果我們想對大寫或小寫字符進行操作，我們可以將“大小寫”屏蔽掉。使用c & 0b00011111or c & 31or ，c & 0x1F我們將始終得到大寫字符的等價物，已經規范化為以 1 開頭。

char  dez  bin        Masking         char  dez  bin         Masking
'A'   65   0100 0001  & 0x1b = 1      'a'   97   0110 0001   & 0x1b = 1
'B'   66   0100 0010  & 0x1b = 2      'b'   98   0110 0010   & 0x1b = 2
'C'   67   0100 0011  & 0x1b = 3      'b'   99   0110 0011   & 0x1b = 3
 . . .

So, if we use an alpha character, mask it, and subtract 1, then we get as a result 0..25 for any upper- or lowercase character.

Additionally, I would like tor repeat the key handling. Positive keys will encrypt a string, negative keys will decrypt a string. But, as said above, negative keys can be transormed into positive ones. Example:

Shifting by  -1  is same as shifting by   25
Shifting by  -2  is same as shifting by   24
Shifting by  -3  is same as shifting by   23
Shifting by  -4  is same as shifting by   22

So,it is very obvious that we can calculate an always positive key by: 26 key. For negative keys, this will give us the above offsets.

And for positve keys, we would have an overflow over 26, which we can elimiate by a modulo 26 division:

'A'-->  0   26 = 26    26 % 26 = 0 
'B'-->  1   26 = 27    27 % 26 = 1 
'C'-->  2   26 = 28    28 % 26 = 2 
'D'-->  3   26 = 29    29 % 26 = 3

--> (c key) % 26 will eliminate overflows and result in the correct new en/decryptd character.

And, if we combine this with the above wisdom for negative keys, we can write: ((26 (key&))&) which will work for all positive and negative keys.

將其與該掩蔽相結合，可以為我們提供以下程式：

const char potentialLowerCaseIndicator = c & 0x20;
const char upperOrLower = c & 0x1F;
const char normalized = upperOrLower - 1;
const int withOffset =  normalized   ((26 (key%26))%26);
const int withOverflowCompensation = withOffset % 26;
const char newUpperCaseCharacter = (char)withOverflowCompensation   'A';
const char result = newUpperCaseCharacter | (potentialLowerCaseIndicator );

當然，上面的許多陳述句都可以轉換為一個 Lambda：

#include <string>
#include <algorithm>
#include <cctype>
#include <iostream>

// Simple function for Caesar encyption/decyption

std::string caesar(const std::string& in, int key) {
    std::string res(in.size(), ' ');

    std::transform(in.begin(), in.end(), res.begin(), [&](char c) {return std::isalpha(c) ? (char)((((c & 31) - 1   ((26   (key % 26)) % 26)) % 26   65) | (c & 32)) : c; });

    return res;
}

int main() {
    std::string test{ "aBcDeF xYzZ" };
    std::cout << caesar(test, 5);
}

最后一個函式也可以變得更詳細以便于理解：

std::string caesar1(const std::string& in, int key) {
    std::string res(in.size(), ' ');

    auto convert = [&](const char c) -> char {
        char result = c;
        if (std::isalpha(c)) {

            // Handling of a negative key (Shift to left). Key will be converted to positive value
            if (key < 0) {
                // limit the key to 0,-1,...,-25
                key = key % 26;
                // Key was negative: Now we have someting between 0 and 26
                key = 26   key;
            };

            // Check and remember if the original character was lower case
            const bool originalIsLower = std::islower(c);

            // We want towork with uppercase only
            const char upperCaseChar = (char)std::toupper(c);

            // But, we want to start with 0 and not with 'A' (65)
            const int normalized = upperCaseChar - 'A';

            // Now add the key
            const int shifted = normalized   key;

            // Addition result maybe bigger then 25, so overflow. Cap it
            const int capped = shifted % 26;

            // Get back a character
            const char convertedUppcase = (char)capped   'A';

            // And set back the original case
            result = originalIsLower ? (char)std::tolower(convertedUppcase) : convertedUppcase;
        }
        return result;
    };
    std::transform(in.begin(), in.end(), res.begin(), convert);
    return res;
}

如果您想查看僅包含最簡單陳述句的解決方案，請參見下文。

#include <iostream>
#include <string>

using namespace std;

string caesar(string in, int key) {

    // Here we will store the resulting encrypted/decrypted string
    string result{};


    // Handling of a negative key (Shift to left). Key will be converted to positive value
    if (key < 0) {
        // limit the key to 0,-1,...,-25
        key = key % 26;
        // Key was negative: Now we have someting between 0 and 26
        key = 26   key;
    };
   
    // Read character by character from the string
    for (unsigned int i = 0; i < in.length();   i) {

        char c = in[i];

        // CHeck for alpha character
        if ((c >= 'A' and c <= 'Z') or (c >= 'a' and c <= 'z')) {

            // Check and remember if the original character was lower case
            bool originalIsLower = (c >= 'a' and c <= 'z');

            // We want to work with uppercase only
            char upperCaseChar = originalIsLower ? c - ('a' - 'A') : c;

            // But, we want to start with 0 and not with 'A' (65)
            int normalized = upperCaseChar - 'A';

            // Now add the key
            int shifted = normalized   key;

            // Addition result maybe bigger then 25, so overflow. Cap it
            int capped = shifted % 26;

            // Get back a character
            char convertedUppcase = (char)capped   'A';

            // And set back the original case
            result  = originalIsLower ? convertedUppcase   ('a' - 'A') : convertedUppcase;

        }
        else
            result  = c;
    }
    return result;
}

int main() {
    string test{ "aBcDeF xYzZ" };
    string encrypted = caesar(test, 5);
    string decrypted = caesar(encrypted, -5);

    cout << "Original:  " << test << '\n';
    cout << "Encrpyted: " << encrypted << '\n';
    cout << "Decrpyted: " << decrypted << '\n';
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/417241.html

標籤：

上一篇：使用BFS的滑動拼圖

下一篇：發夾結構簡單演算法