Example 99. Consider Bitcoins curve secp256k1 again. As we have seen in example 96, it is infeasible to compute elements from the pairing group G2 and as we know from example 93 it is moreover infeasible to do calculations in the extension field F pk. It follows that the Weil pairing is not efficiently computable and that secp256k1 is not pairing friendly. Exercise 84. Consider the curve alt_bn128 from example 73 and the generators g1 and g2 of G1[p] and G2[p] from exercise 83. Write a Sage program that computes the Weil pairing e(g1, g2). 5.5 Hashing to Curves Elliptic curve cryptography frequently requires the ability to hash data onto elliptic curves. If the order of the curve is not a prime number, hashing to prime order subgroups is of importance, 108 475 476 477 478 479 480 481 482 483 CHAPTER 5. ELLIPTIC CURVES

5.5. HASHING TO CURVES too and in the context of pairing-friendly curves, it is sometimes necessary to hash specifically onto the pairing group G1 or G2 as introduced in 5.4.3. As we have seen in section 4.1.7, some general methods are known for hashing into finite cyclic groups and since elliptic curves over finite fields are finite and cyclic groups, those methods can be utilized in this case, too. However, in what follows we want to describe some methods specific to elliptic curves that are frequently used in real-world applications.

5.5.1 Try-and-increment hash functions One of the most straight-forward ways of hashing onto an elliptic curve point in a secure way is to use a cryptographic hash function together with one of the hashing into modular arithmetics methods as described in section 4.2.1. Both constructions can be combined in such a way that the image provides an element of the base field of the elliptic curve together with a single auxiliary bit. The base field element can then be interpreted as the x-coordinate of a potential curve point, and the auxiliary bit can be used to determine one of the two possible y coordinates of that curve point as explained in 5.1.1.2.

Such an approach would be deterministic and easy to implement, and it would conserve the cryptographic properties of the original hash function. However, not all x coordinates generated in such a way will result in quadratic residues when inserted into the defining equation. It follows that not all field elements give rise to actual curve points. In fact, on a prime field, only half of the field elements are quadratic residues. Hence, assuming an even distribution of the hash values in the field, this method would fail to generate a curve point in about half of the attempts. One way to account for this problem is the following so-called try-and-increment method. Instead of simply hashing a binary string s to the field, this method use a try-and-increment hash to the base field as described in 4.2.1.1 in combination with a single auxiliary bit derived from the underlying cryptographic hash function.