Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <blockquote> <p>as long as I keep adding the start point to itself I never reach the point at infinity (O). </p> </blockquote> <p>Could you please post the reference/link where you learned this. I have very limit knowledge of Elliptic curves but I know little bit of Haskell so I tried to see what is going with your code. Very first thing I noticed the use of division and double while you are using modular arithmetic modulo prime p. I am not able to see what you mod'' does so I changed your code little bit and it's working fine for me.</p> <pre><code>type Curve = ( Integer , Integer , Integer ) data Point = P Integer Integer | O deriving (Eq, Read, Show) extendedGcd :: Integer -&gt; Integer -&gt; ( 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 -&gt; Integer -&gt; Integer modInv a b | gcd a b /= 1 = error " gcd is not 1 " | otherwise = d where d = until ( &gt; 0 ) ( + b ) . fst.extendedGcd a $ b addP :: Curve-&gt;Point-&gt;Point-&gt;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 &amp;&amp; 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 </code></pre> <p>Lets take curve y^2 = x^3 + x + 1 modulo 13. Z_13 = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ]. Quadratic residue ( QR ) = [ 0, 1, 3, 4, 9, 10, 12] and Quadratic non residue ( QNR )= [ 2, 5, 6, 7, 8, 11] of Z_13. Take x = 0 and we have y^2 = 1 ( mod 13 ) since 1 is in QR so solution for this equation is 1 and 12. We get two points ( 0, 1 ) and ( 0, 12 ). Putting x = 1, y^2 = 3 ( mod 13 ) so points corresponding to x = 1 is ( 1, 4 ) and ( 1, 9). Putting x=2, y^2 = 11 ( mod 13 ) and 11 is QNR so we don't have solution. Whenever a solution exists, it gives us two points and both are inverse of each other modulo prime p ( 13 in this case ). Total points on given curve is ( 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 ). You can try all the points and see which one generate the whole group. </p> <pre><code> *Main&gt;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&gt; 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] </code></pre> <p>Coming back to Elgamal system<br> 1. Bob chose elliptic curve E( a, b) over GF( p ) or GF ( 2^n ).<br> 2. Bob chose a point on the curve e1( x1, y1 )<br> 3. Bob chose an integer d.<br> 4. Bob calculate e2(x2, y2 ) = d * e1( x1, y1 ).<br> 5. Bob announce E( a, b, p ), e1( x1, y1 ) and e2( x2, y2) as your public key and keeps d as private key<br></p> <p>Encryption. <br> Alice selects P, point on the curve, as her plain text. She chose a random number r and computes C1 = r * e1, C2 = P + r * e2. <br> Decryption.<br> Bob after receiving C1 and C2, computes C2 - d * C1 => P + r * e2 - d * r * e1 <br> => P + r * d * e1 - d * r * e1 => P </p> <p>Edit: You are correct! If you take generator element and keep adding it then you can generate the whole group. See the lecture by Christof Paar[1].<br> [1]<a href="https://www.youtube.com/watch?v=3S9eZRHjP8g&amp;list=PLn_QCKxjl9zmx3VojkDqljZcLCIslz7kB&amp;index=37" rel="nofollow">https://www.youtube.com/watch?v=3S9eZRHjP8g&amp;list=PLn_QCKxjl9zmx3VojkDqljZcLCIslz7kB&amp;index=37</a></p>
    singulars
    1. This table or related slice is empty.
    1. POWhere is the mistake in this Elliptic Curve code
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USkeep_learning
    1. USkeep_learning
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload