问题理解

我们需要从给定的密文 $C$ 和密钥 $(x, S, P)$ 中恢复明文 $M$。加密过程如下：

1. 计算 $d$： [ d = \left\lfloor n^{1.5} + x \right\rfloor \mod n ] 其中 $n$ 是明文或密文的长度。

2. 加密 $C[d]$：

   • $C[d]$ 是 $S$ 中位置与 $M[d]$ 在 $P$ 中的位置相同的符号。
   • 即，找到 $M[d]$ 在 $P$ 中的位置 $pos$，然后 $C[d] = S[pos]$。

3. 加密其他 $C[j]$：

   • 对于 $j \neq d$，$C[j]$ 是 $S$ 中位置等于 $M[j]$ 在 $P$ 中的位置与 $M[(j+1) \mod n]$ 在 $S$ 中的位置的异或。
   • 即，$pos_C[j] = pos_P[M[j]] \oplus pos_S[M[(j+1) \mod n]]$，然后 $C[j] = S[pos_C[j]]$。

解密思路分析

解密的目标是逆向上述过程：

1. 计算 $d$：

   • 同样使用 $d = \left\lfloor n^{1.5} + x \right\rfloor \mod n$。

2. 解密 $M[d]$：

   • $C[d] = S[pos_P[M[d]]]$，因此 $pos_P[M[d]] = pos_S[C[d]]$。
   • 因为 $P$ 是 $S$ 的排列，可以找到 $M[d] = P[pos_S[C[d]]]$。

3. 解密其他 $M[j]$：

   • 对于 $j \neq d$，$pos_C[j] = pos_P[M[j]] \oplus pos_S[M[(j+1) \mod n]]$。
   • 这是一个方程，我们需要解出 $pos_P[M[j]]$ 和 $pos_S[M[(j+1) \mod n]]$。
   • 由于 $pos_S[M[(j+1) \mod n]]$ 是 $M[(j+1) \mod n]$ 在 $S$ 中的位置，我们可以利用后续的 $M$ 值来推断 $pos_S[M[(j+1) \mod n]]$。

解密算法实现

从 $d$ 开始，逆向填充 $M$：

1. 初始化：

   • 读取 $x$, $S$, $P$, $C$。
   • 计算 $n$ 和 $d$。

2. 解密 $M[d]$：

   • 找到 $C[d]$ 在 $S$ 中的位置 $pos$，然后 $M[d] = P[pos]$。

3. 解密其他 $M[j]$：

   • 从 $d-1$ 开始，逆向遍历到 $d$。
   • 对于每个 $i$，计算 $C[i]$ 在 $S$ 中的位置 $temp1$。
   • 计算 $M[(i+1) \mod n]$ 在 $S$ 中的位置 $temp2$。
   • 然后 $M[i] = P[temp1 \oplus temp2]$。

代码实现

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
int main()
{
    int x,i,j;
    while(~scanf("%d",&x))
    {
        char s[35],p[35],c[70],m[70];
        int splen,n,d;
        if(x==0) break;
        scanf("%s\n%s\n%s",s,p,c);
        splen=strlen(s);
        n=strlen(c);
        d=((int)(pow(n,1.5))+x)%n;
        for(i=0;i<splen;i++)
            if(c[d]==s[i])
                m[d]=p[i];
        int temp1,temp2;//分别记录c[i]在s中的位置，与m[(i+1)%n]在s中的位置
        for(i=d-1;(i+n)%n!=d;i--)
        {
            if(i<0)
                i=(i+n)%n;
            for(j=0;j<splen;j++)
                if(c[i]==s[j])
                {
                    temp1=j;
                    break;
                }
            for(j=0;j<splen;j++)
                if(m[(i+1)%n]==s[j])
                {
                    temp2=j;
                    break;
                }
            m[i]=p[temp1^temp2];//运用题解中提到的公式
        }
        for(j=0;j<n;j++)
            printf("%c",m[j]);
        printf("\n");
    }
    return 0;
}

代码解释

1. 输入读取：

   • 读取 $x$, $S$, $P$, $C$。

2. 计算 $d$：

   • 使用 $d = \left\lfloor n^{1.5} + x \right\rfloor \mod n$。

3. 解密 $M[d]$：

   • 找到 $C[d]$ 在 $S$ 中的位置，然后 $M[d] = P[pos]$。

4. 解密其他位置：

   • 对于每个 $i \neq d$：
     • 找到 $C[i]$ 在 $S$ 中的位置 $pos_C$。
     • 找到 $M[(i+1) \mod n]$ 在 $S$ 中的位置 pos_M_next。
     • 计算 pos_P_M_i = pos_C \oplus pos_M_next。
     • M[i] = P[pos_P_M_i]。

5. 输出结果：

   • 打印解密后的 $M$。