Elliptic Curves with the Montgomery-Form and Their Cryptographic Applications

We show that the elliptic curve cryptosystems based on the Montgomery-form EM:BY2 = X3 + AX2 +X are immune to the timing-attacks by using our technique of randomized projective coordinates, while Montgomery originally introduced this type of curves for speeding up the Pollard and Elliptic Curve Methods of integer factorization [Math. Comp. Vol.48, No.177, (1987) pp.243-264].However, it should be noted that not all the elliptic curves have the Montgomery-form, because the order of any elliptic curve with the Montgomery-form is divisible by “4”. Whereas recent ECC-standards [NIST,SEC-1] recommend that the cofactor of elliptic curve should be no greater than 4 for cryptographic applications.Therefore, we present an efficient algorithm for generating Montgomery-form elliptic curve whose cofactor is exactly “4”. Finally, we give the exact consition on the elliptic curves whether they can be represented as a Montgomery-form or not. We consider divisibility by “8” for Montgomery-form elliptic curves.We implement the proposed algorithm and give some numerical examples obtained by this.