为何Java中AES/GCM模式解密的时间复杂度为O(n²)？

通过以下测试代码可以观察到，JDK自带的SunJCE实现中，AES/GCM算法的解密操作存在**二次时间复杂度（O(n²)）**问题：

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.function.BiFunction;

import javax.crypto.Cipher;
import javax.crypto.CipherInputStream;
import javax.crypto.CipherOutputStream;
import javax.crypto.spec.GCMParameterSpec;
import javax.crypto.spec.IvParameterSpec;
import javax.crypto.spec.SecretKeySpec;

public class AES_Test {

    public static void main(String[] args) throws Exception {
        Random r = new Random();
        byte[] key = new byte[32];
        byte[] spec = new byte[12];
        byte[] iv = new byte[16];
        r.nextBytes(key);
        r.nextBytes(spec);
        r.nextBytes(iv);

        List<BiFunction<Integer, SecretKeySpec, Cipher>> cipherCreators = List.of(
            (mode, serverKey) -> {
                GCMParameterSpec eGcmParameterSpec = new GCMParameterSpec(16 * 8, spec);
                try {
                    Cipher eCipher = Cipher.getInstance("AES/GCM/NoPadding");
                    eCipher.init(mode, serverKey, eGcmParameterSpec);
                    return eCipher;
                } catch (Exception e) {
                    throw new RuntimeException(e);
                }
            },
            (mode, serverKey) -> {
                IvParameterSpec ivSpec = new IvParameterSpec(iv);
                Cipher eCipher;
                try {
                    eCipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
                    eCipher.init(mode, serverKey, ivSpec);
                } catch (Exception e) {
                    throw new RuntimeException(e);
                }
                return eCipher;
            },
            (mode, serverKey) -> {
                IvParameterSpec ivSpec = new IvParameterSpec(iv);
                Cipher eCipher;
                try {
                    eCipher = Cipher.getInstance("AES/CTR/NoPadding");
                    eCipher.init(mode, serverKey, ivSpec);
                } catch (Exception e) {
                    throw new RuntimeException(e);
                }
                return eCipher;
            },
            (mode, serverKey) -> {
                IvParameterSpec ivSpec = new IvParameterSpec(iv);
                Cipher eCipher;
                try {
                    eCipher = Cipher.getInstance("AES/CTS/NoPadding");
                    eCipher.init(mode, serverKey, ivSpec);
                } catch (Exception e) {
                    throw new RuntimeException(e);
                }
                return eCipher;
            }
        );

        SecretKeySpec serverKey = new SecretKeySpec(key, "AES");

        for (int j = 0; j < 3; j++) {
            System.out.println("*** Run " + (j + 1) + " ***");
            for (BiFunction<Integer, SecretKeySpec, Cipher> cipherCreator : cipherCreators) {
                for (int i = 1; i <= 32; i *= 2) {
                    byte[] randomBytes = new byte[i * 1024 * 1024];
                    r.nextBytes(randomBytes);
                    long start = System.currentTimeMillis();
                    // Encrypt
                    ByteArrayOutputStream bout = new ByteArrayOutputStream(randomBytes.length);
                    {
                        Cipher encryptCipher = cipherCreator.apply(Cipher.ENCRYPT_MODE, serverKey);
                        ByteArrayInputStream fin = new ByteArrayInputStream(randomBytes);
                        OutputStream cout = new CipherOutputStream(bout, encryptCipher);

                        fin.transferTo(cout);
                        cout.close();
                    }
                    byte[] encBytes = bout.toByteArray();
                    long encrypted = System.currentTimeMillis();
                    // Decrypt
                    {
                        InputStream fin = new ByteArrayInputStream(encBytes);
                        Cipher decryptCipher = cipherCreator.apply(Cipher.DECRYPT_MODE, serverKey);
                        InputStream cin = new CipherInputStream(fin, decryptCipher);
                        bout = new ByteArrayOutputStream(randomBytes.length);

                        cin.transferTo(bout);
                    }
                    long decrypted = System.currentTimeMillis();

                    System.out.println(cipherCreator.apply(Cipher.ENCRYPT_MODE, serverKey).toString() + "  Size=" + i + "M  Encrypted=" + (encrypted - start) + "ms  Decrypted1=" + (decrypted - encrypted) + "ms result1=" + Arrays.equals(randomBytes, bout.toByteArray()));
                }
            }
        }
    }
}

在测试机器上，SunJCE实现的运行结果如下：

*** Run 3 ***
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: SunJCE  Size=1M  Encrypted=13ms  Decrypted1=91ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: SunJCE  Size=2M  Encrypted=25ms  Decrypted1=236ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: SunJCE  Size=4M  Encrypted=56ms  Decrypted1=854ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: SunJCE  Size=8M  Encrypted=104ms  Decrypted1=3552ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: SunJCE  Size=16M  Encrypted=202ms  Decrypted1=13896ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: SunJCE  Size=32M  Encrypted=394ms  Decrypted1=53576ms result1=true

从结果中可以清晰看到，随着输入数据量翻倍，解密耗时近似四倍增长，符合**O(n²)**的时间复杂度特征。

代码中使用ByteArrayOutputStream缓冲输出的逻辑本身是线性时间复杂度（缓冲区每次扩容一倍，总复制操作的时间复杂度为O(n)），因此该性能问题并非由缓冲逻辑导致，而是JDK SunJCE实现的特有问题。对比使用BouncyCastle（BC）实现的测试结果，解密耗时与数据量呈线性增长：

*** Run 3 ***
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: BC  Size=1M  Encrypted=15ms  Decrypted1=16ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: BC  Size=2M  Encrypted=28ms  Decrypted1=30ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: BC  Size=4M  Encrypted=51ms  Decrypted1=59ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: BC  Size=8M  Encrypted=111ms  Decrypted1=124ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: BC  Size=16M  Encrypted=196ms  Decrypted1=222ms result1=true
Cipher.AES/GCM/NoPadding, mode: encryption, algorithm from: BC  Size=32M  Encrypted=362ms  Decrypted1=443ms result1=true

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