为何rsaKeygen()生成的密钥长度恒为19？扩大范围程序挂起如何解决？

问题情况 #

• 运行rsaKeygen()生成的密钥长度固定为19位，无法满足常规明文的加密需求
• 尝试扩大p和q的取值范围后，程序直接卡滞（挂起）
• 19位密钥长度过短，使用pkcs1_v1_5_pad处理普通长度明文时，会直接触发"Message is too long for the given key size"错误

密钥生成函数代码 #

function rsaKeygen()
  p = math.random(50000,100000)
  while not isprime(p) do
    p = math.random(1,1000)
  end
  q = math.random(1,1000)
  while not isprime(q) do
    q = math.random(50000,100000)
  end
  local n = p*q
  totientN = carmichael(n)
  e = 2^16+1
  local d = 1%totientN/e
  p,q,totientN = nil,nil,nil
  return e,d,n
end

PKCS1_v1_5填充函数代码 #

function pkcs1_v1_5_pad(message,key_size)
  print(key_size)
  local block_size = key_size/8
  local message_length = #message
  local padding_length = block_size - message_length - 3
  if padding_length < 0 then
    error("Message is too long for the given key size")
  end
  local padding = string.rep("\x00",padding_length)
  local padded_message = string.char(0x00)..string.char(0x02)..padding..string.char(0x00)..message
  return padded_message
end

问题根源与解决办法 #

密钥长度固定的原因 #

看密钥生成逻辑就能明白：

• 查找p时，初始取50000-100000的数，若不是素数直接切换到1-1000的范围找
• 查找q时反过来，先从1-1000找，找不到就切换到50000-100000的范围
  最终p和q必定一个是1-1000的小素数，一个是50000-100000的中等素数，两者乘积的范围完全固定，密钥长度自然无法变化。

扩大范围后程序挂起的原因 #

一是原代码逻辑错误，扩大范围后只要第一次随机数不是素数，就直接跳回小区间，等于没真正扩大范围；二是如果真的在大区间找素数，isprime函数大概率是低效的试除法，大素数的试除检测会慢到离谱，直接导致程序卡滞。

填充函数适配失败的原因 #

PKCS#1 v1.5要求填充后的块长度等于密钥的字节数（即key_size/8），19比特的密钥仅对应2个多字节，连基础填充位都不够，更别说容纳明文，必须使用至少1024比特（128字节）的密钥才能适配常规明文。

具体修复步骤 #

1. 修正密钥生成逻辑

将素数查找改为在同一个大区间内反复随机，同时修正私钥d的计算（原代码的1%totientN/e完全错误，不是求模逆元的正确方式）：

function rsaKeygen()
  -- 生成1024比特级别的素数，对应十进制约308位，区间可按需调整
  local min = 2^511
  local max = 2^512 - 1
  -- 查找第一个素数p
  local p = math.random(min, max)
  while not isprime(p) do
    p = math.random(min, max)
  end
  -- 查找第二个素数q，确保q≠p
  local q = math.random(min, max)
  while not isprime(q) or q == p do
    q = math.random(min, max)
  end
  local n = p * q
  local totientN = carmichael(n)
  local e = 2^16 + 1 -- 65537，业界常用公钥指数，兼顾安全性与效率
  -- 用扩展欧几里得算法求e的模totientN逆元d，这是私钥核心
  local d = modinv(e, totientN)
  p, q, totientN = nil, nil, nil
  return e, d, n
end

需要自行实现modinv函数（基于扩展欧几里得算法）来计算模逆元，这是RSA私钥生成的关键步骤。

2. 替换高效素数检测算法

放弃试除法检测大素数，换成米勒-拉宾素性测试——这是概率性检测算法，速度快且重复几次测试后准确率接近100%，能避免大区间找素数时的卡滞问题。

3. 计算正确的密钥比特长度

填充函数需要的key_size是密钥n的二进制比特长度，可用以下函数计算：

function bit_length(n)
  local bits = 0
  while n > 0 do
    bits = bits + 1
    n = math.floor(n / 2)
  end
  return bits
end
-- 使用示例
local e, d, n = rsaKeygen()
local key_size = bit_length(n)
local padded_msg = pkcs1_v1_5_pad("你的明文内容", key_size)

4. 修正填充函数的规范问题

原填充函数用全\x00做填充，不符合PKCS#1 v1.5规范（要求填充字节为0x01到0xFF之间的非零值），修正后的函数：

function pkcs1_v1_5_pad(message, key_size)
  local block_size = math.floor(key_size / 8)
  -- 密钥长度最好为8的倍数，此处做兼容处理
  local message_length = #message
  local padding_length = block_size - message_length - 3
  if padding_length < 0 then
    error("Message is too long for the given key size")
  end
  -- 生成随机非零填充字节
  local padding = ""
  for i = 1, padding_length do
    padding = padding .. string.char(math.random(1, 255))
  end
  local padded_message = string.char(0x00) .. string.char(0x02) .. padding .. string.char(0x00) .. message
  return padded_message
end

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