bash - bash中的RSA算法（私钥计算）

Question

在给出 p、q 和 e 时，寻求有关如何在 bash 脚本“d”中计算 RSA 密钥的帮助。

虽然我知道这个查询以前出现过，但我似乎找到的只是在给出 p、q 和 e 时计算 RSA 私钥的理论建议。

我正在尝试将 bash 脚本中的计算放在一起，因此真的很想对 bash 中可能的计算进行一些解释（使用 expr 或 bc）

我找到了一个基本上建议以下内容的网站；（'t' 是 p*q 的总称，或者更确切地说是 'n' 的总称）

d=$(echo "((2 * $t) + 1) / $e" | bc)

但这似乎只适用于该特定情况，并且在尝试不同情况时没有提供正确的输出。

关于如何为此计算编写 bash 公式的任何帮助？

Answer 1

从 RSA 的定义

|e*d| = 1 (mod fi(p*q))

其中 fi(n) 是欧拉函数

所以你需要在这个模中计算 e 的倒数。不要忘记检查 GCD(e,fi(p*q))=1 或者你可能在给定的模数中找不到 e 的反转。

您可以通过使用扩展欧几里得算法来实现这一点。网络上有很多伪代码。您需要更多帮助吗？