标签离散对数的存档

如何计算曲线?

您可能听说过使用曲线的加密方法,更具体地说是椭圆曲线。但是,您如何加密,即通过一条曲线将一条清晰的消息转换成一条隐藏的消息呢?

椭圆曲线

所讨论的曲线是椭圆曲线,即方程式的曲线 y2 = x3 + a x + b 要么 ab 是数字,例如 y2 = x3 – 2 x 可以画的+1。我们得到下图。

曲线是满足上述等式的坐标x和y的点M的集合,即y2 = x3-2 x + 1。

与椭圆的关系是间接的,因为它涉及到其长度的计算,而椭圆是在其直径之一上“变平”的圆。在这一点上,我们将不再赘述,因为它与密码学无关。优点是我们可以定义将曲线的点转换为另一点的操作。我们正在接近加密的想法...尚未实现。

椭圆曲线上的群定律

椭圆曲线的优点是您可以在其中定义定律。下图显示了如何在曲线的两个点P和Q上关联一个用P + Q表示的点。

在一般情况下,我们画一条线PQ。它在R点与曲线相交,P + Q是R相对于x轴的对称。如果P = Q,则PQ是曲线上P处的切线。为了使该定义在所有情况下均有效,我们需要在曲线上附加一个无穷大点,用0表示。如果PQ是垂直的,则P + Q = 0。

我们证明,该定律具有数字相加的通常属性,即缔合性,可交换性,中性点(无穷大点)的存在以及任意点对称(精确地相对于x轴对称) )。

注意:有关计算的详细信息可以在我的网站上找到:  这里

加密

为了进行加密,我们不在实数字段上考虑椭圆曲线,而在诸如Z / N的有限字段上考虑椭圆曲线,其中N是素数。曲线将具有有限数量的点。起点是可以将文本转换为曲线上的一系列点。这相当于用字母书写与曲线具有点数一样多的符号。请注意,根本的问题并不简单,但从理论上讲,加密则包括变换曲线上的一个点。秘密密钥由曲线上的一个点P和一个整数(例如3)组成。然后,我们计算P’= 3P。然后,公共密钥就是一对点(P,P’)。为了加密点M,加密器选择一个整数,例如23,并传输由以下定义的对(U,V):U = 23 P和V = M + 23 P’。知道第一个数字(这里为3)就足以找到M,因为M = V-3U。

离散对数

为了找到所选的数字,在我们的示例中为3,知道P和P’,就足以知道如何求解方程:P’= 3P。动词“足够”的使用不应引起误解。这并不意味着它很简单,而是如果您知道如何做,就知道如何解密。然后将数字3称为离散对数,如果使用上面的加法表示法则很难直观地理解。使用组运算的乘法表示法,由于方程式随后被写成,因此这变得更加常见:P’= P3。在一组通常的数字中,3对应于P的基本对数P,因此名称在有限组内。目前,这个问题被认为是非常困难的。据估计,用于椭圆曲线的200位密钥比用于RSA方法的1024位密钥更安全。由于执行椭圆曲线并不复杂,因此对于具有很少功率的芯片卡来说,这是一个很大的优势,并且密钥的大小对性能有很大的影响。缺点是双重的。一方面,椭圆函数理论是复杂且​​相对较新的。不排除我们可以解决离散对数的问题。另一方面,椭圆曲线密码技术已成为全球众多专利的主题。这可能会使使用变得昂贵!