Java实现Affine Cypher时解密结果与原文不符的问题求助

问题根源 #

解密函数中计算(val - b)时可能得到负数，而Java的负数模运算结果仍为负数。比如测试用例中，加密后的字符b对应数值1，减去b=2得到-1，乘以a=7的逆元15后是-15，-15 % 26在Java中结果为-15，加上97后得到ASCII码82（对应大写字母R），这就是解密结果出现错误的直接原因。

修复方案 #

1. 修正解密函数的模运算逻辑
   确保模运算结果始终为0-25之间的非负整数，修改解密函数中的计算代码：

   // 原代码
   int D = ((inv(a, 26)*(val-b))%26);
   // 修改为
   int temp = inv(a, 26) * (val - b);
   int D = (temp % 26 + 26) % 26;
   

   通过(temp % 26 + 26) % 26的处理，无论temp是正还是负，最终结果都会落在合法的字母数值范围内。

2. 优化Scanner输入逻辑
   原代码创建了两个Scanner实例，且nextInt()后未处理残留的换行符，可能导致输入读取异常。优化后的输入代码如下：

   Scanner sc = new Scanner(System.in);
   System.out.println("Enter key(a,b): ");
   a = sc.nextInt();
   b = sc.nextInt();
   sc.nextLine(); // 消耗nextInt()留下的换行符，避免nextLine读取空串
   System.out.print("Enter String: ");
   String word = sc.nextLine();
   sc.close();
   

3. 增加密钥合法性检查（可选）
   Affine密码要求a必须与26互质（即最大公约数为1），否则无法解密。可以添加gcd函数检查密钥合法性：

   public static int gcd(int num1, int num2) {
       while (num2 != 0) {
           int temp = num2;
           num2 = num1 % num2;
           num1 = temp;
       }
       return num1;
   }
   

   在main函数中添加检查：

   if (gcd(a, 26) != 1) {
       System.out.println("Error: a必须与26互质！");
       sc.close();
       return;
   }
   

修复后的完整代码 #

import java.util.Scanner;
public class abcd {
    public static int a, b;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter key(a,b): ");
        a = sc.nextInt();
        b = sc.nextInt();
        
        // 检查a与26是否互质
        if (gcd(a, 26) != 1) {
            System.out.println("Error: a必须与26互质！");
            sc.close();
            return;
        }
        
        sc.nextLine();
        System.out.print("Enter String: ");
        String word = sc.nextLine();
        sc.close();

        System.out.println("Cyphered text: " + cypher(word));
        System.out.println("Decyphered text: " + decypher(cypher(word)));
    }
    
    public static String cypher(String plaintext) {
        String CT = "";
        for (int i = 0; i < plaintext.length(); i++) {
            char x = plaintext.charAt(i);
            int val = x - 97;
            int C = ((a * val + b) % 26);
            char n = (char) (C + 97);
            CT = CT + n;
        }
        return CT;
    }
    
    public static int inv(int a, int b) {
        a = a % b;
        for (int x = 1; x < 26; x++) {
            if ((a * x) % 26 == 1) {
                return x;
            }
        }
        return 1;
    }
    
    public static String decypher(String cyphertext) {
        String t = "";
        int aInv = inv(a, 26); // 提前计算逆元，避免循环重复计算
        for (int i = 0; i < cyphertext.length(); i++) {
            char x = cyphertext.charAt(i);
            int val = x - 97;
            int temp = aInv * (val - b);
            int D = (temp % 26 + 26) % 26;
            char n = (char) (D + 97);
            t = t + n;
        }
        return t;
    }
    
    public static int gcd(int num1, int num2) {
        while (num2 != 0) {
            int temp = num2;
            num2 = num1 % num2;
            num1 = temp;
        }
        return num1;
    }
}

测试验证 #

输入密钥7 2和字符串hello，加密结果为zebbw，解密结果将正确返回hello，与原文本一致。

内容的提问来源于stack exchange，提问作者user21141364