初音ミクの消失

Vigenère密码题解

字数统计: 1.1k阅读时长: 4 min
2018/12/06 Share

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<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

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;
}

原文作者:mrh929

原文链接:https://mrh1s.top/posts/4c789951/

发表日期:December 6th 2018, 11:37:40 pm

更新日期:May 5th 2019, 1:43:55 pm

版权声明:本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

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