2

我正在尝试在haskell中编写一个带有椭圆曲线的elgamal实现。但是我的点加法函数存在一些问题：只要我不断将起点添加到自身，我就永远不会到达无穷大（O）点。这是我的代码：

addP :: Curve->Point->Point->Point
addP _ O O = O
addP _ O p = p
addP _ p O = p
addP curve@(a,b,p) (P x1 y1) (P x2 y2) | x1 == x2 && y1 == -y2 = O
                                       | otherwise = P x3 ((m*(x1-x3)-y1) `mod''` p)
    where x3 = (((m*m)-x1-x2) `mod''` p)
          m | x1 /= x2 = (y2-y1)/(x2-x1)
            | otherwise = (3*(x1*x1)+a)/(2*y1)

其中曲线定义为

-- first double=a, second double=b, third double=p in y^2=x^3+ax+b mod p
type Curve = (Double, Double, Double)

点定义为

data Point = P Double Double |
             P
             deriving (Eq, Read, Show)

有谁知道我做错了什么？

4

1 回答 1

3

只要我不断将起点添加到自身，我就永远不会到达无穷大（O）点。

您能否发布您在其中学到的参考/链接。我对椭圆曲线的了解非常有限，但我对 Haskell 知之甚少，所以我试图看看你的代码是怎么回事。在使用模数模素数 p 时，我首先注意到除法和双精度的使用。我无法看到你的 mod'' 做了什么，所以我稍微更改了你的代码，它对我来说工作正常。

type Curve = ( Integer , Integer , Integer )
data Point = P Integer Integer | O
         deriving (Eq, Read, Show)


extendedGcd :: Integer -> Integer -> ( Integer , Integer )
extendedGcd a b
  | b == 0 = ( 1 , 0 )
  | otherwise = ( t , s - q * t ) where
      ( q , r ) = quotRem a b 
      ( s , t ) = extendedGcd b r


modInv :: Integer -> Integer -> Integer
modInv  a b
  | gcd a b /= 1 = error " gcd is not 1 "
  | otherwise = d where
     d = until ( > 0 ) ( + b  ) . fst.extendedGcd a $ b


addP :: Curve->Point->Point->Point
addP _ O O = O 
addP _ O p = p 
addP _ p O = p 
addP ( a, b, p ) ( P x1 y1 ) ( P x2 y2 ) 
    | x1 == x2 && mod ( y1 + y2 ) p == 0 = O 
    | otherwise = P x3 ( mod ( m * ( x1 - x3 ) - y1 ) p ) where
            m | x1 /= x2 = ( mod ( y2 - y1 ) p ) * modInv ( mod ( x2 - x1 ) p ) p
              | otherwise = ( 3 * x1 * x1 + a ) * modInv  ( 2*y1 ) p
            x3 = mod ( m * m - x1 - x2 ) p

让我们取曲线 y^2 = x^3 + x + 1 模 13。Z_13 = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ]。Z_13 的二次余数 ( QR ) = [ 0, 1, 3, 4, 9, 10, 12] 和二次非余数 ( QNR )= [ 2, 5, 6, 7, 8, 11]。取 x = 0，我们有 y^2 = 1 ( mod 13 )，因为 1 在 QR 中，所以这个方程的解是 1 和 12。我们得到两个点 (0, 1) 和 (0, 12)。把 x = 1, y^2 = 3 ( mod 13 ) 所以对应于 x = 1 的点是 (1, 4) 和 (1, 9)。把 x=2, y^2 = 11 ( mod 13 ) 和 11 是 QNR 所以我们没有解决方案。每当存在解决方案时，它都会给我们两个点，并且两者都是模素数 p 的倒数（在这种情况下为 13）。给定曲线上的总点数为 (0, 1), (0, 12), (1, 4), (1, 9), (4, 2), (4, 11), (5, 1), (5 , 12), (7, 0), (7, 0), (8, 1), (8, 12), (10, 6), (10, 7), (11, 2), (11, 11 ）。

 *Main>take 20 . iterate ( addP ( 1 , 1 , 13 )  ( P 7 0 ) ) $ ( P 7 0  )
 [P 7 0,O,P 7 0,O,P 7 0,O,P 7 0,O,P 7 0,O,P 7 0,O,P 7 0,O,P 7 0,O,P 7 0,O,P 7 0,O]
 *Main> take 20 . iterate ( addP ( 1 , 1 , 13 )  ( P 0 12 ) ) $ ( P 0 12  )
 [P 0 12,P 10 6,P 7 0,P 10 7,P 0 1,O,P 0 12,P 10 6,P 7 0,P 10 7,P 0 1,O,P 0 12,P 10 6,P 7 0,P 10 7,P 0 1,O,P 0 12,P 10 6]

回到 Elgamal 系统 1。Bob
选择椭圆曲线 E(a,b) 而不是 GF(p) 或 GF(2^n)。
2. Bob 选择了曲线 e1(x1, y1) 上的一个点
3. Bob 选择了一个整数 d。
4. Bob 计算 e2(x2, y2 ) = d * e1( x1, y1 )。
5. Bob 宣布 E( a, b, p ), e1( x1, y1 ) 和 e2( x2, y2) 作为你的公钥，并保留 d 作为私钥

加密。
Alice 选择曲线上的点 P 作为她的纯文本。她选择一个随机数 r 并计算 C1 = r * e1，C2 = P + r * e2。
解密。
Bob 收到 C1 和 C2 后，计算 C2 - d * C1 => P + r * e2 - d * r * e1
=> P + r * d * e1 - d * r * e1 => P

编辑：你是对的！如果您使用生成器元素并继续添加它，那么您可以生成整个组。参见 Christof Paar[1] 的讲座。
[1] https://www.youtube.com/watch?v=3S9eZRHjP8g&list=PLn_QCKxjl9zmx3VojkDqljZcLCIslz7kB&index=37

于 2013-09-13T14:27:52.117 回答