Homework 1 · Part 1

Example App: Public-Key Cryptography PRIVATE KEY → PUBLIC KEY in Ethereum

Ethereum turns a private key k into a public key Q with one operation: elliptic-curve scalar multiplication Q = kG on secp256k1. This page does the same on the toy curve y² = x³ + 7 (mod 17), animates the algorithm step by step, and runs statistical experiments on the outputs.

01

The toy curve

secp256k1, the curve used by Bitcoin and Ethereum, is y² = x³ + 7 over the prime field Fp with p = 2²⁵⁶ − 2³² − 977. The toy curve keeps the same equation but uses p = 17, so every point fits on a 17 × 17 grid.

The points of the curve, together with a point at infinity O, form a finite abelian group. Its size is #E = 18, and the base point G = (1, 5) has order 9: 9G = O, so the multiples of G repeat with period 9.

PointOrderIn ⟨G⟩Multiple of G
02

Point addition

The group law is the chord-and-tangent rule. Draw the line through P and Q, find the third intersection with the curve, and reflect it across the x-axis. Over Fp every division is a multiplication by a modular inverse, computed with the extended Euclidean algorithm.

When P and Q are the same point (doubling, P + P = 2P) there is no line through two distinct points: use the tangent to the curve at P instead, then continue in the same way.

slope, P ≠ Qλ = (y₂ − y₁) · (x₂ − x₁)⁻¹ slope, P = Qλ = (3x₁² + a) · (2y₁)⁻¹ result xx₃ = λ² − x₁ − x₂ result yy₃ = λ(x₁ − x₃) − y₁ all computations mod p

Special cases: P + O = P, and P + (−P) = O, where −(x, y) = (x, −y mod p) (the line is vertical and "meets the curve at infinity").

The program on the right adds any two points of the toy curve and prints every step of the computation. It starts with G + G = 2G.

P + Q 

          

        

      

    


    
    

      

        
03
Computing Q = kG

        
Scalar multiplication is repeated addition, kG = G + G + … + G.
          Adding one G at a time costs k − 1 additions. Double-and-add reads the bits of k and costs at most
          2·log₂k operations. This is what makes secp256k1 practical with k ≈ 2²⁵⁶.
          For example, if we take the base point G = (1, 5) and the private key k = 6,
          we get the toy public key Q = 6G = (5, 8).

        

          
          
          
Method
            

              
              
            

          

          

            
            
            
          

        

        

          

          

            

              Toy public key
              (5, 8)
              Q = 6G
            

            

            
The output is the same for every k with the same value of k mod ord(G).
              The ≈2²⁵⁶ example is the order of secp256k1's group, which on the toy curve reduces to a tiny scalar.

          

        

      

    


    
    

      

        
04
Slow motion: the algorithm, step by step

        
Each step draws the modular line through the operands (it wraps around the grid, because
          coordinates live mod p), marks the third intersection −R, and reflects it to R.

        

          

            
            

              curve point
              in ⟨G⟩
              operands
              result R
              line y = λx + c (mod p)
            

          

          

            

              
              
              
Algorithm
                

                  
                  
                

              

            

            

            

              
              
              
              
            

            

            
    
          
    
        
    
      
    
    
    

    
    
    
      
    
        
    05
    Statistical exploration
    
        
    Run the experiment for many private keys and look at the public keys as data. The example
          curve is p = 17. The larger curves use the same equation with prime group order, as on secp256k1, and give the statistics more room.
    

        
    
          
    
            
            
            
    Private keys
              
    
                
                
              
    
            
    
            
            
          
    
          
    
        
    

        
    

        
    1 · Distribution of coordinates
    
        
    Bars show how often each x (or y) value appears in the sample. The line shows the expected count if public keys were uniform
          over ⟨G⟩. Not every residue mod p is a valid x-coordinate (only about half are), so "uniform over Fp" is the wrong null hypothesis.
    
        
    
          
    x-coordinate
    
          
    y-coordinate
    
        
    

        
    2 · Distribution of bits
    
        
    Fraction of 1s at each bit position of the coordinates (MSB on the left). A hash function would give ≈ 0.5 everywhere.
          Coordinates are numbers below p, so the top bits are biased whenever p is not close to a power of two.
    
        
    
          
    Bits of x
    share of 1s per bit position · line at 0.5
    
          
    Bits of y
    share of 1s per bit position · line at 0.5
    
        
    

        
    3 · Input vs output
    
        
    Each dot is one private key k plotted against the x-coordinate of kG. In sweep mode on p = 17 the period of G is visible at once.
          On larger curves the cloud looks structureless and the correlation coefficients are close to 0. Look closer in sweep mode, though:
          (n − k)G = −kG has the same x-coordinate, so the pattern is mirrored around k = n/2 and repeats every n.
    
        
    
          
    k vs x(kG)
    
          
    Consecutive keys: x(kG) vs x((k+1)G)
    neighbouring inputs, unrelated-looking outputs
    
        
    

        
    4 · Avalanche: flip one bit of k
    
        
    For random k, flip one random bit of the private key, recompute the public key, and count how many output bits change.
          The same experiment with SHA-256 serves as the reference for a hash function. The ideal is half the bits, following Binomial(w, ½).
          On p = 1051 the mean falls below 50%: coordinates take 11 bits but stay below 1051, so the top bit is almost always 0 and rarely flips.
    
        
    
          
    EC scalar multiplication · changed bits of x‖y
    
          
    SHA-256 of k · changed bits of the digest
    
        
    
      
    
    
    

    
    
    
      
    
        
    06
    Discussion: one-way function vs hash function
    
        
    
          
    
            
    PropertyEC scalar multiplicationCryptographic hashMatters for a one-way function?
    
            
              
    DeterministicYesYesYes. Same key, same public key, every time.
    
              
    Easy forwardYes, O(log k) with double-and-addYesYes. Required by definition.
    
              
    Hard to invertECDLP, about √n workPreimage resistanceYes, the defining property. Fails on toy curves, where trying every k is enough.
    
              
    Uniform output for a uniform inputUniform over ⟨G⟩ (bijection)≈ uniform over {0,1}²⁵⁶Yes, as a consequence. Q leaks nothing beyond its own value. Tested by chi-square over ⟨G⟩, not over Fp.
    
              
    Injective / no collisionsBijective on [0, n)No: compresses, so collisions existNot required. For hashes the requirement is that collisions are hard to find.
    
              
    Uniform bits, unbiased bit positionsNo: x < p, only ~½ of x valid, y fixed by x up to signYesHash-specific. This is why ECDH secrets and public keys are hashed before being used as keys or addresses.
    
              
    Avalanche effectLooks present on large curvesDesign goal (SAC)Hash-specific. For EC it is a side effect and hides a predictable relation.
    
              
    No input/output correlation, no algebraic structureNo: homomorphism (a+b)G = aG + bGBehaves like a random oracleHash-specific. For public-key crypto the structure is essential.
    
              
    Fixed-length output for any inputInput is a scalar mod nYesHash-specific (compression, domain extension).
    
                
          
    
        
    

        
    
          
    
            
    What the experiments show
    
            
      
              
    • p = 17 is degenerate. With G = (1, 5), only 8 public keys exist. x takes 4 values ({1, 2, 5, 12}), each exactly twice per period.
                Every statistic is fully determined by the cycle of length 9, and in sweep mode the scatter plot is a repeating pattern.
      • 
              
    • The base point matters. Choosing G of order 2, 3 or 6 shrinks the key space further. A generator of order 18, such as (6, 6), reaches every point.
                Real curves use prime order so that every G ≠ O generates the whole group.
      • 
              
    • Large prime-order curves look random. Chi-square tests over ⟨G⟩ do not reject uniformity, correlations are ≈ 0, and the bit-flip
                experiment changes about half of the output bits. The top-bit bias remains, caused by the range [0, p) and not by a weakness.
      • 
            
    
          
    
          
    
            
    Why that is not the same as a hash
    
            
    A hash function is designed to destroy structure: it should behave like a random function, so that
              knowing H(m) says nothing about H(m′) for any related m′. Avalanche, bit balance and decorrelation are
              symptoms of that goal, and they can be measured statistically.
    
            
    Scalar multiplication is designed to keep structure. It is a group homomorphism
              k ↦ kG from Zn to ⟨G⟩. This structure is what enables ECDSA signatures, Diffie–Hellman,
              and BIP-32's public-key derivation in Part 2 (child public key = parent public key + t·G).
              Its security rests only on the hardness of the ECDLP. That is not a statistical property: the outputs can pass every
              test of section 05 and still satisfy exact algebraic relations.
    
            
    Takeaway: statistical tests can refute randomness but cannot prove one-wayness.
              The toy curve passes some tests and is trivially invertible. secp256k1 fails the "no structure" test by design and is still believed one-way.