Vigenère密码题解

发布于 2018-12-06  51 次阅读


08:Vigenère密码

总时间限制:

1000ms

内存限制:

65536kB

描述

16世纪法国外交家Blaise de Vigenère设计了一种多表密码加密算法——Vigenère密码。Vigenère密码的加密解密算法简单易用,且破译难度比较高,曾在美国南北战争中为南军所广泛使用。

在密码学中,我们称需要加密的信息为明文,用M表示;称加密后的信息为密文,用C表示;而密钥是一种参数,是将明文转换为密文或将密文转换为明文的算法中输入的数据,记为k。在Vigenère密码中,密钥k是一个字母串,k=k1k2…kn。当明文M=m1m2…mn时,得到的密文C=c1c2…cn,其中ci=mi®ki,运算®的规则如下表所示:

Vigenère加密在操作时需要注意:

  1. ®运算忽略参与运算的字母的大小写,并保持字母在明文M中的大小写形式;

  2. 当明文M的长度大于密钥k的长度时,将密钥k重复使用。

例如,明文M=Helloworld,密钥k=abc时,密文C=Hfnlpyosnd。

明文 H e l l o w o r l d
密钥 a b c a b c a b c a
密文 H f n l p y o s n d

 

输入

输入共2行。
第一行为一个字符串,表示密钥k,长度不超过100,其中仅包含大小写字母。第二行为一个字符串,表示经加密后的密文,长度不超过1000,其中仅包含大小写字母。

对于100%的数据,输入的密钥的长度不超过100,输入的密文的长度不超过1000,且都仅包含英文字母。

输出

输出共1行,一个字符串,表示输入密钥和密文所对应的明文。

样例输入

CompleteVictory

Yvqgpxaimmklongnzfwpvxmniytm

样例输出

Wherethereisawillthereisaway

来源

NOIP2012复赛 提高组 第一题

题解:注意本题是由密文解密为原文。由于密钥和密文需要进行相互运算,所以转换大小写是必不可少的,题目有要求原文大小写与密文一致,所以我们可以用一个数组

int miwen_x[2000] 来储存原文大小写的数据

读入密文、密钥,转换大小写并且记录密文的大小写状况

 

接着就是解密数据了,让我们来观察一下Vigenère密码的规律吧

本表指 一对密钥与原文可以加密成密文,现在要翻译密文,也就是知道对应的点,也知道了y轴坐标,求x轴坐标。

1.     当密文≥密钥时,我们发现数据是依次递增的,则此时ans[i]= miwen[i]-key[j]+'a'

2.     当密文<密钥时,数据由最右端向左依次递减,此时ans[i]= 'z'-(key[j]-miwen[i]-1)

j的意义在后面。

 

注意这里还有一个易错点,密钥的长度可能小于密文的长度,那么当密钥较短时就要运用循环多次使用此密钥

int j=0;

 并且在每次循环后

j++;

if(j==strlen(key))

      j=0;

最后通过miwen_x[i]的值将原文的大小写形式恢复原样

这样就解决此问题了

 

本题总思路:

1.     读入密钥、密文并转换成小写(大写也可),同时记录密文的大小写情况

2.     运用算法算出原文

3.     通过大小写情况恢复原文的大小写

#include
#include
#include
#include

int change(int i)//大小写转换 
{
    return (i>='A'&&i<='Z')?i+'a'-'A':i;
}


int main()
{
    char key[120];
    char miwen[1200];
    int miwen_x[1200];//密文大小写 1小写 2大写 
    scanf("%s %s",key,miwen);
    int len=strlen(key);
    for(int i=0;i<=len-1;i++)
        key[i]=change(key[i]);
    for(int i=0;i<=strlen(miwen)-1;i++)
    {
        if(miwen[i]>='A'&&miwen[i]<='Z')
            miwen_x[i]=2;
        else
            miwen_x[i]=1;
        miwen[i]=change(miwen[i]);
    }
    
    char ans[1200];
    int j=0;
    for(int i=0;i<=strlen(miwen)-1;i++)
    {
        if(miwen[i]>=key[j])
            ans[i]=miwen[i]-key[j]+'a';
        else
            ans[i]='z'-(key[j]-miwen[i]-1);
        if(miwen_x[i]==2)
            ans[i]=ans[i]-('a'-'A');
        j++;
        if(j==len)
            j=0;
    }
    ans[strlen(miwen)]=0;
    printf("%s",ans);
    
            
    return 0;
}