一个关于CDH算法的问题

Question

假设有人给了你一个解决CDH问题的算法:它以g, g^a, g^b和g^ab作为输入。展示如何使用它来破解Elgamal加密。

Answer 1

使用给定的算法来破解Elgamal加密，首先可以求出g^0、g^1、g^2...g^(ab-1)，然后将它们与g^a和g^b进行比较，如果有相同的数值，则求出a或b。另外，也可以使用费马小定理来求出a和b，如i为模数，将g^i mod p代入ax + by = i，式中求解x和y即可得到a和b。