An Inconvenient Truth

It’s the time to be aware, and respond to THIS!!!

Let’s go into action!

Characteristic of a ring

The characteristic of a ring is the number of times you must add the multiplicative identity element in order to get the additive identity element.

If adding the multiplicative identity element to itself, no matter how many times, never gives us the additive identity element, we say the characteristic is 0. Otherwise, there must exist an integer p such that p × n = 0 for all n. The value of p is then the characteristic of the ring.

In a ring of characteristic 2, the elements 2, 4, etc., are all equal to 0. In a ring of characteristic 3, the elements 3, 6, etc., are all equal to 0.

Curves avoided for cryptography

Supersingular curves are to be avoided for cryptography because they are vulnerable to the MOV attack. (more about it later)

As with the supersingular curves, elliptic curves that are singular are to be avoided for cryptography .

Supersingularity and singularity

Supersingularity is not to be confused with singularity.

When an elliptic curve is defined over real numbers, singularity of the curve is related to its smoothness. More specifically, a curve is singular if its slope at a point is not defined.

Supersingularity, on the other hand, is related to the order of E2^n and how this order relates to the number of points in the underlying finite field.

Why GF(2^n)?

Binary finite fields more convenient for hardware implementations because the elements of GF (2^n) can be represented by n-bit binary code words. Thus GF(2^n) is common for hardware implementations.
The addition operation in GF (2^n) is like the XOR operation on bit fields. That is x + x = 0 for all x ∈ GF (2^n). This implies that a finite field of form GF (2^n) is of characteristic 2.

NSA’s ECC License Agreement with Certicom

Several important things about ECC and some standards on GF(p) or GF(2^m) from this document :

What is excluded from an NSA sublicense?
The field is restricted to GF(p) where p is a prime number greater than 2^255.
If you wish to use smaller field size or the binary field GF(2^m) in your products, then these products would be excluded from the sublicense.

Why the GF(p) field size?
GF(p) was chosen because it has been well studied over the last 20 years. For national security applications, the NSA would like to see key sizes of at least 256 bits which is why they specify that p is a prime number greater than 2^255.

Why did the NSA not license the binary field GF(2^m)?

The binary field has been well studied over the last 20 years as well and is perfectly secure; however we believe the NSA wanted to limit the implementation choices. The NSA’s stated goal is to foster interoperability amongst secure communications equipment used across various government organizations. By limiting the implementation choices, this interoperability is easier to achieve.

What is Suite B?
The NSA announced Suite B at the RSA Conference February 2005. Suite B has two different levels of security, one for classified information and one for sensitive but unclassified information. The algorithms are as follows:

Why has the NSA defined a Suite B?
We believe Suite B was defined to take advantage of the cryptographic strength of ECC, and to narrow the choices in crypto algorithms. One of the goals is to facilitate sharing of information securely between government organizations which can only be accomplished by setting clear cryptographic standards for systems.
We believe another of the goals is to address the issue of homogeneous cryptographic strengths for symmetric and asymmetric algorithms. For example AES at 128 bits should be paired with ECC at 256 bits and SHA at 256 bits in order to have the whole system at one cryptographic level. Today there are no such rules, and as a result, there are widespread poor cryptographic practices such as using RSA 1024 to exchange keys for AES 128.

Why does the NSA like ECC?

ECC is the only proven pubic key technology that scales in a practical way over time. As computing power increases, it becomes easier to break all cryptosystems so cryptographic keys must increase in size to maintain their strength. The NIST chart below demonstrates this clearly. As you can see, in order to match the AES key strength at 256 bits, you would need to use RSA keys of size 15360 bits. Keys at this size are unusable. With ECC you can use a key size of 512 bits to offer equivalent security.

Why has the US Government endorsed ECC for both classified and sensitive but unclassified?

We believe the NSA is trying to promote the notion of sharing information securely between Government departments at all levels of communication for Homeland Security. This was a key point in the presentation by Mr. Daniel G. Wolf, the National Security Agency’s Director of Information Assurance, at the 14th Annual RSA Conference in 2005. Setting clearly defined cryptographic standards & protocols are crucial for interoperability and making the sharing of information securely a reality.

Is the US alone in selecting ECC?
No. The NESSIE project (New European Schemes for Signatures, Integrity and Encryption) (2000-2003) did extensive evaluation on crypto algorithms. For more information, visit: https://www.cosic.esat.kuleuven.ac.be/nessie/ They recommend ECDSA as a signature scheme and published a chart of key size recommendations that proposes even larger keys than the one above for RSA algorithms.
In addition, in 2001, the Government of Japan formed the CRYPTREC Evaluation Committee which is composed of eminent Japanese cryptographers. They have aggressively evaluated various cryptographic techniques to recommend the optimum cryptographic techniques necessary for the security of future e-Government systems. They recommend a number of ECC-based protocols including ECDSA and ECDH. http://www.ipa.go.jp/security/enc/CRYPTREC/index-e.html
Is ECC found in standards?
Yes. ECC is found in many standards. Here is a brief list.

Projects planned

These are the “projects” we (me and Intan) agreed to do:

1. Do the same thing as Baier for F(2^m)

2. Find the connection between non maximal imaginary quadratic order and elliptic curve

3. Find the effect of the reduction on finite fields

Wish us luck!

Introduction to Cryptography – Johannes A. Buchmann

A new reference for the research. Written by the author of several papers have been used as references. A must read piece of excellent work of the supervisor of Harald Baier while he was doing his dissertation.

Characteristic of a field

The order of a finite field is the number of elements in the field. There exists a finite field F of order q if and only if q is a prime power, i. e. , q=p^m where p is a prime number called the characteristic of F, and m is a positive integer.

If m=1, then F is called a prime field. If m >= 2, then F is called an extension field. For any prime power q, there is essentially only one finite field of order q; informally, this means that any two finite fields of order q are structurally the same except that the labelling used to represent the field elements may be different.

Any two finite fields of order q are isomorphic and denote such a field by Fq.

About Group, Ring and Field

Group:

G1) Closure under addition [if a and b belong to S, then a+b is also in S]

G2) Associativity of addition [a+(b+c) = (a+b)+c for all a, b, c in S]

G3) Additive identity [There is an element 0 in R such that a+0=0+a=a for all a in S]

G4) Additive inverse [For each a in S there is an element -a in S such that a+(-a)=(-a)+a=0]

Abelian Group:

AG) Commutativity of addition [a+b=b+a for all a, b in S]

Ring:

R1) Closure under multiplication [If a and b belong to S, then ab is also in S]

R2) Associativity of multiplication [a(bc)=(ab)c for all a, b, c in S]

R3) Distributive laws [a(b+c)=ab+ac for all a, b, c in S (a+b)c=ac+bc for all a,b, c in S]

Commutative Ring:

CR) Commutativity of multiplication [ab=ba for all a, b in S]

Integral Domain:

ID1) Multiplicative identity [There is an element 1 in S sucht that a1=1a=a for all a in S]

ID2) No zero divisors [If a, b in S and ab = 0, then either a=0 or b=0]

Field:

F) Multiplicative invers [if a belongs to S and a != 0, there is an element 1/a in S such that (a)(1/a)=(1/a)(a)=1]

[more updating ...]