P2636 密码破解者题解

Luxe877 · 2023-08-15 19:53:56 · 题解

原题链接：P2636 密码破解者

本题是一道~~比较水~~简单字符串模拟题，题意也比较好理解。

大致题意

给你经过 n 重加密的密文，以及密文的加密顺序及种类 K，让你反推原始明文并输出。

1.栅栏密码

其加密方式如下：以栏数 X=2 为例，设原明文为 DistortedFate，其长度为 len=13。

将该明文分为 2 个一段（其中最后一段若不能分为 2 个一段，则独立成段）,即 Di st or te dF at e。

然后对于每段，每次选出第 1 个字母加入到密文字符串中，即得 明文剩余部分：i t r e F t，密文：Dsotdae。

以此类推，经过 2 次选取后该明文便被加密为密文 DsotdaeitreFt。

我们给密文的每一个字符标上它们在明文中的下标，如下：

密文字符：D s o t d  a  e i t r e  F t
对应下标：1 3 5 7 9 11 13 2 4 6 8 10 12

我们可以发现，下标的增长是有规律的，以原先加密时选取的次数为段,下标呈等差数列形式增长，公差为 X，下标增长到 \ge len 时换为下一段，每段的第一个字符的下标在区间 \lbrack1,X\rbrack 之间。

因此，根据这样推断的结果，我们可以写出解栅栏密码的程序如下：

void fenceup(int x)
{
    int len=strlen(pw+1);
    char solve[10002];
    int duan=1;
    int p=duan;
    for(int i=1;i<=len;i++)
    {
        solve[p]=pw[i];
        p+=x;
        if(p>len)
        {
            duan++;
            p=duan;
        }
    }
    for(int i=1;i<=len;i++)
    {
        pw[i]=solve[i];
    }
}

2.维吉尼亚(Vigenère) 密码

其加密方式见此题：P1079 [NOIP2012 提高组] Vigenère 密码

由加密方式倒推，可以得到解密方式如下：

密文字符-密钥字符=明文字符

自然，和原加密时一样，解密时可能会导致减出来的 ASCII 码值小于字母，导致破译失败，因此在减的时候要同时 +26 与取模，便可得出以下代码：

void vigne(char scw[])
{
    int len=strlen(pw+1),l=strlen(scw),tmp=0;
    char uncode[10002];
    bool upb;
    for(int i=1;i<=len;i++)
    {
        upb=false;
        if(pw[i]>='A'&&pw[i]<='Z')
        {
            upb=true;
            pw[i]=pw[i]-'A'+'a';
        }
        if(scw[tmp]>='A'&&scw[tmp]<='Z')
        {
            scw[tmp]=scw[tmp]-'A'+'a';
        }
        uncode[i]=(pw[i]-scw[tmp]+26)%26+'a';
        if(upb)
        {
            uncode[i]=uncode[i]-'a'+'A';
        }
        tmp=(tmp+1)%l;
    }
    for(int i=1;i<=len;i++)
    {
        pw[i]=uncode[i];
    }
}

3.QWE 键盘码

其加密方式较为简单，由键盘上 Q 键开始为 A， W 键为 B，以此类推至全部字母键，只需要提前写好对应密文的数组访问即可，代码如下：

void keybd()
{
    char word[52]={'k','x','v','m','c','n','o','p','h','q','r','s','z','y','i','j','a','d','l','e','g','w','b','u','f','t'};
    int len=strlen(pw+1);
    bool upb;
    for(int i=1;i<=len;i++)
    {
        upb=false;
        if(pw[i]>='A'&&pw[i]<='Z')
        {
            pw[i]=pw[i]-'A'+'a';
            upb=true;
        }
        pw[i]=word[pw[i]-'a'];
        if(upb)
        {
            pw[i]=pw[i]-'a'+'A';
        }
    }
}

最后，处理好输入输出即可得出正解。代码如下：

#include<bits/stdc++.h>
using namespace std;
int n;
char pw[10002];
struct nd{
    int type;
    char spw[1002];
    int mvw;
}uns[1012];
void fenceup(int x)//分 X 段 
{
    int len=strlen(pw+1);
    char solve[10002];
    int duan=1;//段数
    int p=duan;//密文下标
    for(int i=1;i<=len;i++)
    {
        solve[p]=pw[i];
        p+=x;
        if(p>len)//下标超过明文长度时换为下一行统计
        {
            duan++;
            p=duan;
        }
    }
    for(int i=1;i<=len;i++)
    {
        pw[i]=solve[i];
    }
//  cout<<pw+1<<endl;
}
void vigne(char scw[])
{
    int len=strlen(pw+1),l=strlen(scw),tmp=0;
    char uncode[10002];
    bool upb;
    for(int i=1;i<=len;i++)
    {
        upb=false;
        if(pw[i]>='A'&&pw[i]<='Z')//大小写处理
        {
            upb=true;
            pw[i]=pw[i]-'A'+'a';
        }
        if(scw[tmp]>='A'&&scw[tmp]<='Z')//大小写处理
        {
            scw[tmp]=scw[tmp]-'A'+'a';
        }
        uncode[i]=(pw[i]-scw[tmp]+26)%26+'a';//解密(注意不要忘了+26、%26、+'a')
        if(upb)//大小写处理
        {
            uncode[i]=uncode[i]-'a'+'A';
        }
        tmp=(tmp+1)%l;
    }
    for(int i=1;i<=len;i++)
    {
        pw[i]=uncode[i];
    }
//  cout<<pw+1<<endl;
}
void keybd()
{
    char word[52]={'k','x','v','m','c','n','o','p','h','q','r','s','z','y','i','j','a','d','l','e','g','w','b','u','f','t'};//存储对应密文
    int len=strlen(pw+1);
    bool upb;//大写区分 
    for(int i=1;i<=len;i++)
    {
        upb=false;
        if(pw[i]>='A'&&pw[i]<='Z')//大小写处理
        {
            pw[i]=pw[i]-'A'+'a';
            upb=true;
        }
        pw[i]=word[pw[i]-'a'];
        if(upb)//大小写处理
        {
            pw[i]=pw[i]-'a'+'A';
        }
    }
//  cout<<pw+1<<endl;
}
int main()
{
    cin>>n>>pw+1;
    for(int i=1;i<=n;i++)
    {
        cin>>uns[i].type;
        if(uns[i].type==1)
        {
            cin>>uns[i].mvw;
            continue;
        }
        if(uns[i].type==2)
        {
            cin>>uns[i].spw+1;
        }
    }
    for(int i=n;i>=1;i--)
    {
        if(uns[i].type==1)
        {
            fenceup(uns[i].mvw);
            continue;
        }
        if(uns[i].type==2)
        {
            vigne(uns[i].spw+1);
            continue;
        }
        if(uns[i].type==3)
        {
            keybd();
            continue;
        }
    }
    cout<<pw+1<<endl;
    return 0;
}

注意事项（坑点）

1. 大小写要注意转换，解密时要化为同一形式。
1. Vigenère 密码解密时要加和取模 26。
1. 不要输错 QWE 键盘码的对应密文。
1. 建议使用 char a[] 类型存储明文和密文，不建议使用 string 类型（本人的悲伤遭遇）。

后记

本题解为萌新的首篇题解，LateX 在编辑的时候加载得不太好，审核大大求过。

P2636 密码破解者 题解