Finding vulnerable curves over finite fields of characteristic 2 by pairing reduction

摘要

In this paper, we aim at sustaining the claim that curve-based cryptographic schemes over finite fields of characteristic 2 do not provide enough security. We present algorithms to find all the possible supersingular elliptic curves which can be embedded into a predefined finite field. We also consider the case of hyperelliptic curves with genus 2, including both supersingular and ordinary cases. As computational examples, we show even the DLP on a 3060-bit elliptic curve and the DLP on Jacobians of a 255-bit hyperelliptic curve can be solved by embedding to a 6120-bit extension field.In this paper, we aim at sustaining the claim that curve-based cryptographic schemes over finite fields of characteristic 2 do not provide enough security. We present algorithms to find all the possible supersingular elliptic curves which can be embedded into a predefined finite field. We also consider the case of hyperelliptic curves with genus 2, including both supersingular and ordinary cases. As computational examples, we show even the DLP on a 3060-bit elliptic curve and the DLP on Jacobians of a 255-bit hyperelliptic curve can be solved by embedding to a 6120-bit extension field.