Elliptic curves, as used in cryptography, are essentially points bounded by a finite prime field which display group properties that facilitate their usage in a cryptosystem. The Discrete Log Problem (DLP) - based on a large prime order subgroup of (Zp)* - constitutes the essence of Elliptic Curve Cryptography (ECC) and can be summed up as such; find an integer, k, such that Q = kP where k = logp(Q) and P, Q ∈ (Zp)*.
Compared to the Integer Factorisation Problem - upon which RSA is constructed - the DLP achieves a greater level of complexity in terms of resistance to attack. This project seeks to describe the mathematical properties that enable ECC to outperform RSA, culminating in the construction of a software system to demonstrate ECC’s ability to securely encipher and decipher files and text, according to the National Security Agency’s (NSA) Cryptographic Interoperability Strategy (CIS) or Suite B Cryptography.
Investigation into the Cryptographic Properties of Elliptic Curves
Defined over a Prime Field
16th June 2014
Abstract
Elliptic curves, as used in cryptography, are essentially points bounded by a finite prime field which
display group properties that facilitate their usage in a cryptosystem. The Discrete Log Problem (DLP) -
based on a large prime order subgroup of (Z
p
) - constitutes the essence of Elliptic Curve Cryptography
(ECC) and can be summed up as such; find an integer, k, such that Q = kP where k = log
p
(Q) and
P, Q (Z
p
) . Compared to the Integer Factorisation Problem - upon which RSA is constructed - the DLP
achieves a greater level of complexity in terms of resistance to attack. This project seeks to describe the
mathematical properties that enable ECC to outperform RSA, culminating in the construction of a software
system to demonstrate ECC's ability to securely encipher and decipher files and text, according to the
National Security Agency's (NSA) Cryptographic Interoperability Strategy (CIS) or Suite B Cryptography.
"One of the most singular characteristics of the art of deciphering is the strong conviction possessed
by every person, even moderately acquainted with it, that he is able to construct a cipher which
nobody else can decipher."
- Charles Babbage
1
Contents
1
Project Plan and Scope
6
1.1
To investigate the mathematical properties of elliptic curves as they relate to cryptography . .
6
1.2
To analyse ECC as an alternate to RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.3
To identify and select an appropriate elliptic curve for use in a cryptosystem.
. . . . . . . . .
6
1.4
To design and develop a cryptographic software system as a vehicle for this investigation . . .
6
1.5
Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.5.1
Semester 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.5.2
Semester 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2
Literature Survey
9
2.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.2
Mathematical construction of elliptic curves for use in a Cryptosystem . . . . . . . . . . . . .
9
2.3
ECC as an alternate to RSA
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.4
Elliptic curve parameter selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
3
Requirements
17
3.1
Primary Software Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3.2
Functional Requirements
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3.2.1
Public/Private key pair generation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3.2.2
Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3.2.3
Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3.3
Non-Functional Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
4
Design
19
4.1
Class Diagrams
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
4.1.1
Encrypt Class Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
4.1.2
Decrypt Class Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
4.1.3
KeyGen Class Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
4.1.4
Process Text Class Diagram
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
4.1.5
Class Structure
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
4.2
Sequence Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
4.2.1
Process Text Sequence Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
4.2.2
Encrypt Sequence Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
4.2.3
Decrypt Sequence Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
4.2.4
toHex method Sequence Diagram
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
5
Implementation
28
5.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
5.2
Week 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
5.3
Week 2: Graphical User Interface (GUI) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
5.4
Week 3 - 4: Key Pair Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
5.5
Weeks 5 - 7: Encryption
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
5.6
Week 8: Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
5.7
Week 9: Key Import/Export
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
6
Conclusion
37
6.1
Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
6.2
Further Work
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
References
38
2
List of Figures
1
Graph showing point addition on an elliptic curve . . . . . . . . . . . . . . . . . . . . . . . .
10
2
Graph showing point doubling on an elliptic curve
. . . . . . . . . . . . . . . . . . . . . . .
11
3
Graph of the all the points on the elliptic curve y
2
= x
3
+ (-3x) + 7 mod
929
The graph was
constructed in MATLAB
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
4
Encrypt Class Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
5
Decrypt Class Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
6
Key Generation Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
7
Encrypt/Decrypt Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
8
Class Structure
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
9
Process Text Sequence Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
10
Encrypt Sequence Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
11
Decrypt Sequence Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
12
toHex Sequence Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
13
Main GUI window . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
14
GUI showing the Key-Pair generator with generated keys. . . . . . . . . . . . . . . . . . . . .
29
15
GUI showing the Encrypt File function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
16
GUI showing the View Key function
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
17
Code snippet showing the P384 curve parameters . . . . . . . . . . . . . . . . . . . . . . . .
31
18
Return values for the P384CurveParameters() method. . . . . . . . . . . . . . . . . . . . . .
31
19
ECPoint and ECFieldElement classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
20
ECDomainParameters construction.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
21
Initialising the KeyPairGenerator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
22
Private and public key extraction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
23
Private and Public Key examples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
24
Cipher Block Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
25
Cipher Block Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
26
Encryption engine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
27
Derivation and Encoding functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
28
Cipher Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
29
Initialising the Encryption Engine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
30
The file byte array is encrypted and saved to the file system. . . . . . . . . . . . . . . . . . .
34
31
CBC Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
32
Decryption initialiser. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
33
Decrypted byte array. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
34
Key import/export attempt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
35
Kryo import method. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
3
List of Tables
1
Project Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2
Semester 8 Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3
NIST public key size recommendation for RSA and ECC
. . . . . . . . . . . . . . . . . . . .
15
List of Algorithms
1
RSA key generation algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
4
5
1
Project Plan and Scope
1.1
To investigate the mathematical properties of elliptic curves as they relate to
cryptography
Elliptic curves, as they relate to cryptosystems, have very little to do with ellipses or curves, but rather the
algebraic structure of the curves over finite fields, and can be considered more a group of points on the
curve that, abstractly, hold a topological equivalency to a torus, and have coordinates (x,y) which satisfy the
following equation in general -
y
2
+ a
1
xy + a
3
y = x
3
+ a
2
x
2
+ a
4
x + a
6
, ...a
i
GF
(1.1)
or more specifically for a Prime field -
y
3
= x
2
+ ax + b · · · · · · x, y, a, b GF (p)
(1.2)
and a Koblitz binary curve -
y
2
+ xy = x
3
+ ax + 1, GF (2
m
)
(1.3)
where the discriminant satisfies the following -
= 4a
3
+ 27b
2
= 0
(1.4)
A thorough analysis of curve construction will be conducted in order to gain a complete understanding of
the cryptographic use of elliptic curves.
1.2
To analyse ECC as an alternate to RSA
A comparative analysis of ECC and RSA will be undertaken in order to fully understand the implications of
continued use of RSA or the future adoption of ECC. Both systems will be scrutinized under key strength,
resistance to attack and NSA/NIST recommendations.
1.3
To identify and select an appropriate elliptic curve for use in a cryptosystem.
The National Institute of Standards and Technology (NIST) recommends the use of 15 elliptic curves, five
reside in the Prime field and ten in the Binary field, of which five are Koblitz curves. The recommended Prime
field curves will be examined and compared to the requirements of the NSA's Suite B security requirements,
after which a curve will be selected and justified.
1.4
To design and develop a cryptographic software system as a vehicle for this
investigation
A Java based system is to be created that will provide the user with the ability to construct an aysmmetric
cipher key pair based on Elliptic Curves and use the keys to encrypt and decrypt any desired file or text.
6
1.5
Plan
1.5.1
Semester 7
Component
1
2
3
4
5
6
7
8
9
10
11
12
13
Project Proposal
1
1
1
Scope & Plan
1
1
Literature Survey
1
1
1
1
1
1
1
1
1
ECC versus RSA
1
1
1
1
Curve construction
1
1
1
1
1
1
Prime Field versus Koblitz Curve
1
1
1
1
1
1
1
Curve Selection
1
1
1
Software Requirements
1
1
1
1
1
Design
1
1
1
1
1
Oral Presentation
1
Table 1: Project Plan
7
1.5.2
Semester 8
Component
1
2
3
4
5
6
7
8
9
10
11
12
13
Software Development
1
1
1
1
1
1
1
1
1
Develop Plan
1
Create GUI
1
Key Pair Generation Method
1
1
Encryption Method
1
1
Decryption Method
1
1
Key import/export
1
Testing
1
1
1
1
1
1
1
1
Draft Dissertation
1
Final Dissertation
1
Oral Presentation
1
Table 2: Semester 8 Plan
· Week 1: A development plan will be created to manage the temporal and work units of the project.
Note that, aside from the testing phase, which iterates repeatedly, all other phases proceed concurrently.
· Week 2: A GUI (Graphical User Interface) will be designed and constructed according to the require-
ments in 3.2.1. Note that minor changes may occur owing to aesthetics.
· Week 3 - 4: The key pair generation method(s) will be implemented. Both native and imported
libraries will be used to achieve an Elliptic Curve Diffie Helman system. Code will be tested.
· Week 5 - 6: The encryption method(s) will be created using the generated/imported EC public key.
Code will be tested.
· Week 7 - 8: The decryption method will be created using the generated/imported EC private key.
Code will be tested.
· Week 9: The methods allowing the import or export of a key pair. Code will be tested.
· Week 10: Full integration testing will be conducted on all aspects of the code. A security audit will
be conducted to assure secure coding techniques were successfully employed.
· Week 11: Draft dissertation will be completed and reviewed.
· Week 12: Final dissertation will be completed.
· Week 13: Prepare and conduct oral presentation.
8
2
Literature Survey
2.1
Introduction
Elliptic curves have been studied for hundreds of years, however the use of elliptic curves in cryptography
was independently proposed by Koblitz and Miller in the 1980's. The cryptographic use of the curves centres
around the properties that emerge when the curves are defined over a finite field, and thus form a group. The
following literature survey seeks to describe the cryptographic properties of elliptic curves and the possibility
of a replacement for RSA.
2.2
Mathematical construction of elliptic curves for use in a Cryptosystem
Formally, an Elliptic curve may be defined as -
E (F ) = {} {(x, y)} F.F | y
2
+ ... = x
3
+ ... |
(2.1)
That is, an elliptic curve E defined over a finite field F is the union of the point at infinity and
the coordinates (x,y) which belong to the subset of F.F and both x and y satisfy the general
Weirstrass equation -
y
2
+ a
1
xy + a
3
y = x
3
+ a
2
x
2
+ a
4
x + a
6
, a
i
GF
(2.2)
The modular discriminant = 4A
3
+ 27B
2
= 0 If and only if there are no double roots, then
the curve E can be used to form a group.
As elliptic curves are underpinned by group theory, given that, according to the Lagrange and Mordell theorems,
a finite field of prime order is an abelian group, they adhere to certain group axioms. Given two points P, Q,
in a finite prime field (GF (p)), there exists a third point P + Q = R (mod p) and the following relations hold
true for all P, Q, R in (GF (p))
· P + Q = Q + P - Commutative Law
· (P + Q) + R = P + (Q + R)- Associative Law
· P + O = O + P = P where O is the point at infinity. This is the identity element of the group
· There exists (-P ) such that -P + P = P + (-P ) = O - This is the inverse of the group
· P + Q + R = O
· P + Q + Q = O
· P + Q + O = O
Accordingly, the points on the curve may be manipulated with group operations, point addition/doubling and
scalar multiplication, and it is these operations that lie at core of elliptic curve cryptography.
Point addition, P + Q, and point doubling, P + P = 2P , are implemented as follows -
Let P = (x
1
, y
1
)and Q = (x
2
, y
2
)
If P = Q; then P + Q = -R = (x
3
, y
3
); then R = (x
3
, -y
3
)
Thus (x
3
, y
3
) is given as -
x
3
=
2
- x
1
- x
2
(2.3)
y
3
= (x
1
- x
3
) - y
1
(2.4)
If P = Q; then P = P ; then P + P = 2P = (x
3
, y
3
)
Thus (x
3
, y
3
) is given as -
x
3
=
2
- 2x
1
(2.5)
9
y
3
= y
1
+ (x
1
- x
3
)
(2.6)
where , the slope of the line through P and Q, is given by
=
y
2
- y
1
x
2
- x
1
If P=Q
(2.7)
=
3x
2
1
+ a
2y
1
If P=Q
(2.8)
Then consider the following trivial examples for point addition and point doubling on a curve
1
-
Take the curve(E)y
2
= x
3
- ax + b where a = -3 and b = 7
pick the points P = (-1.62, 2.77) and Q = (2.77, 4.47)
=
4.47 - 2.77
2.77 - (-1.62)
=
2.7
4.39
= 0.615
x
3
= 0.615
2
- (-1.62) - 2.27 = -1.01
y
3
= 0.615(-1.62 - (-1.01)) - 2.27 = 3.0
-R = (-1.01, 3.0)
R = (-1.01, -3.0) -R is reflected on the y-axis - inversion
Figure 1: Graph showing point addition on an elliptic curve
1
This example is trivial in that the arithmetic is not implemented in a finite field and would not be used in a cryptosystem.
This is due to the infinite decimal expansion properties of R which would generate an inaccurate round-off error.
10
Point doubling is carried out in the following fashion -
Pick a point P = (2.39, 3.67)
=
3(2.39)
2
+ (-3)
2(3.67)
= 1.92596
x
3
= 1.925926
2
- 2(2.39) = -1.09
y
3
= 1.925926(2.39 - (-1.09)) - 3.67 = -3.0
-R = (-1.09, -3.0)
R = (-1.09, 3)
P + P = 2P = (-1.09, 3.0)
Figure 2: Graph showing point doubling on an elliptic curve
Scalar multiplication defines the process of obtaining a point kP by utilising a combination of both the
point addition and point doubling operations in the fashion P + P = 2P, P + 2P = 3P...nP .
Consider the elliptic curve E(GF
p
) y
2
= x
3
- (-3x) + 7 mod
7
the following are the values for 7P -
(0, 0) (2, 3) (2, 4) (3, 2) (3, 5) (6, 3) (6, 4)
11
The previous example had a modulus of 7 and thus contains only a small number of points. Consider the
following graph of the points on the curve E(GF
p
) with modulus of 929 , incidentally, a palindromic prime -
Figure 3: Graph of the all the points on the elliptic curve y
2
= x
3
+ (-3x) + 7 mod
929
The graph was
constructed in MATLAB
As can be seen in Figure 3, as the the modulus p the number of points increases dramatically and
can be derived from Hasse's famous theorem -
Let E be an elliptic curve
y
2
= x
3
- Ax + B
with A, B F (p)
Then
|#E(F
p
) - (p - 1)| 2
p
When a sufficiently large value is selected for the modulus, the inverse operation, i.e. the discrete log-
arithm, becomes very hard to compute, with the best known algorithm, Pollard's modified - method,
[Gallant et al.(1999)Gallant, Lambert, and Vanstone] having a running time of O(
(n)
2
) , where each it-
eration is one scalar multiplication.This intractability of scalar multiplication lies at the heart of the Elliptic
Curve Discrete Logarithm Problem which in turn allows for the use of elliptic curves in cryptography. The
ECDLP can be stated as such;
Let E be an elliptic curve over the finite field GF (p) and let P and Q be points in E(GF (p)).
The Elliptic Curve Discrete Logarithm Problem is in finding an integer, k, such that Q = kP
where k = log
p
(Q).
Thus, elliptic curves may be modified for use in a discrete log cryptosystem. Diffie-Hellman is a key exchange
protocol that utilises the discrete log problem as it's underlying hardness and is implemented with elliptic
curves as follows;
12
Alice and Bob both agree on a random point, P , residing in a curve of GF (p). Alice then chooses
a secret value k
1
and computes the point k
1
P and sends it to Bob. Bob, likewise chooses k
2
and com-
putes k
2
P sending it to Alice. The shared key then becomes k
1
k
2
P . An attacker would need to calcu-
late the shared key knowing only P, k
1
P, k
2
P , this is the Diffie-Hellman discrete log problem for elliptic
curves.[McGrew et al.(2011)McGrew, Igoe, Salter, Cisco Systems, and National Security Agency, ElGamal(1985)]
13
2.3
ECC as an alternate to RSA
Asymmetric key cryptography, such as ECC and RSA, utilise a mathematically linked public/private key pair
for encryption and decryption. The public key, as the name suggests, is openly available to everyone and is
used for encryption. The private key, known only to the user, is used for decryption. As shown previously, ECC
relies on the discrete log problem in contrast to RSA, the most common asymmetric key algorithm, which
uses the difficulty of factoring large primes as its underlying hardness, the so-called Factorisation Problem.
Consider the following RSA key generation algorithm;
Algorithm 1 RSA key generation algorithm
Select two large primes p, q
Compute n = pq
Choose an integer e, such that e > (n), gcd(e(n)) 1,
where , Euler's Totient function = (p - 1)(q - 1)
e becomes the public exponent
Calculate d = d
-1
= e(mod (n)) where d
-1
is the multiplicative inverse
d is used as the private key
Supposing Bob wants to encrypt a message to Alice, he receives Alice's public key which consists of the prime
modulus n and the public exponent e. Bob calculates c = m
e
(mod n) , where c is the cipher text and m is
the plain text, and sends c to Alice. In order to decrypt the message, Alice uses her private key d such that
m = c
d
(mod n), thus obtaining the original message. If an attacker gains access to the modulus n and (n)
then factoring the modulus into p and q, which breaks the system, becomes trivial. Observe the following
example, where the prime modulus n and (n) are known;
N = 768899
(n) = 767136
let p =
n
q
, q =
n
p
, n = pq, (n) = (p - 1)(q - 1)
pq = 768899, (p - 1)(q - 1) = 767136
pq - p - 1 + 1 = 767136
768899 - q + 1 - 767136 = p
let k = 768899 + 1 - 767136
k = 1764
let k - q = p
1764 - q = p
1764 - q =
n
q
1764 - q =
768899
q
1764 - q
2
= 768899
q
2
- 1764q + 768899 = 0 solve the quadratic -
1764 ±
(-1764)
2
- 4.1(768899)
2(1)
1764 + 190
2
= 977
1764 - 190
2
= 787
p = 977, q = 787
q = 977, p = 787
14
Integer factorisation, as shown, lies at the core of RSA and its difficulty can be described as such - Supposing
an n-bit number that is the product of two large primes, there exists no known algorithm that can factor n in
polynomial time O(n log n).
The best known method for factorisation is the General Number Field Sieve which has a running time of
((c + o(1))n
1
3
log
2
3
n)
(2.9)
RSA-768, which has 232 digits, was successfully factored in 2009 by Thorsten Kleinjung et.al. However,
the largest RSA prime, RSA-2048, has 617 digits and look set to remain secure until future advances in
computational power or prime factorisation become available. Therefore, provided the key length is sufficiently
large, RSA provides comparable security to ECC in terms of mathematical construction. It must be noted,
however, that while ECC provides comparable security with RSA, the differences in key size are considerable.
Consider the table below, it can be seen that for a 512 bit ECC key the comparable RSA key size is 15,360 bits.
This fact is important when implementing a cryptosystem in a device with power or computational constraints,
such as embedded systems, as competing resources may have an adverse affect on the operational status of
the device thus breaking the security triangle of authentication, availability and integrity.
ECC Key size (bits)
RSA key size (bits)
Key size ratio
Symmetric key size (bits)
160
1024
1:6
80
224
2048
1:10
112
256
3072
1:15
128
384
7680
1:20
192
512
15360
1:30
256
Table 3: NIST public key size recommendation for RSA and ECC
Resistance to attack is another area that sees ECC out-perform RSA. As was previously shown, ECC
is susceptible to Pollards - method while RSA is susceptible to the General Number Field Sieve. The
complexity of an attack against ECC, however, grows exponentially, O(2
n
) with the key size, in comparison to
an RSA attack which only grows sub-exponentially O(2
log n
log log n
). This has implications for the future use of
RSA due to the ever increasing level of computational power being brought to bear on breaking the systems,
as continuously increasing the key size will eventually become infeasible due to computational overheads. ECC
with its exponential increase, seems much more likely to remain secure, and baring some future mathematical
breakthrough in the discrete log problem, should continue to scale with increasing demands.
The previous comparisons are given greater weight due to RSA's exclusion from the NSA's Cryptographic
Interoperability Strategy (CIS) or Suite B Cryptography.
The CIS sets out recommended cryptographic
protocols for use in Secret, Top Secret and Sensitive Compartmented Information (SCI) environments. For
the protection of Top Secret information, the NSA recommends "AES with 256-bit keys, Elliptic Curve Public
Key Cryptography using the 384-bit prime modulus elliptic curve as specified in FIPS PUB 186-3 and SHA-384
are required to protect classified information at the TOP SECRET level".[National Security Agency(2009)]
15
2.4
Elliptic curve parameter selection
As stated previously, NIST[National Institute of Standards and Technology(2010)] and the NSA recommends
the use of the P-384 curve parameters for use in sensitive environments. Comparing P-384 with the RSA
alternative, one can clearly see the difference in key strength, a 7,680-bit RSA key would be required to
provide similar security. This difference allows for less channel overhead when exchanging keys over a comm
link, and while the computational cost-per-bit is greater, due to the mathematical complexity of ECC, the
extra security more than compensates.
As the NSA recommends the use of the P-384 curve for Top Secret data, it can be assumed that the
security of the curve is sound, however it cannot rule out the possibility that there exists some inbuilt method
for compromising the system which is known only to the NSA. This has not affected the choice of curve for
this investigation as defeating the NSA is not an objective.
Listed below are the chosen curve parameters selected for use in an ECC prime field cryptosystem - ;
The prime modulus P 384 = 2
384
- 2
128
- 2
96
+ 2
32
- 1
P = 39402006196394479212279040100143613805079739270465
44666794829340424572177149687032904726608825893800
1861606973112319
The parameter a = P 384 - 3
a = 3940200619639447921227904010014361380507973927046544
666794829340424572177149687032904726608825893800
1861606973112316
The parameter b
b = 27580193559959705877849011840389048093056905856361
56852142870730198868924130986086513626076488374510
7765439761230575
The base point G = (X
G
, Y
G
)
X
g
= 26247035095799689268623156744566981891852923491109
21338781561590092551885473805008902238805397571978
6650872476732087
Y
G
= 83257109614890299855467512895201081792878530488613
15594709205902480503199884419224438643760392947333
078086511627871
Base point G in hexadecimal
X
G
= aa87ca22 be8b0537 8eb1c71e f320ad74 6e1d3b62 8ba79b98
59f741e0 82542a38 5502f25d bf55296c 3a545e38 72760aB7
Y
G
= 3617de4a 96262c6f 5d9e98bf 9292dc29 f8f41dbd 289a147c
e9da3113 b5f0b8c0 0a60b1ce 1d7e819d 7a431d7c 90ea0e5F
The order q, of the point G and the curve group E
q = 39402006196394479212279040100143613805079739270465
44666794690527962765939911326356939895630815229491
3554433653942643
16
3
Requirements
3.1
Primary Software Functions
The software artefact for this investigation shall be an encryption/decryption system that utilises elliptic curves
to provide the security. The system shall enable a user to construct a public/private key pair and to then
encrypt/decrypt a document using this key pair. The key pair will be constructed using the Diffie-Helman
Elliptic Curve protocol with encryption being carried out using the Elliptic Curve Integrated Encryption Scheme
(ECIES) using the parameters described in 2.4. The system should show the user the generated key pair and
store them in a secure key ring, the key pair should also be exportable. As the system is designed to be run
on a desktop or laptop and not a mobile device, resource constraints and operational overheads are not an
issue.
3.2
Functional Requirements
The following are the functional requirements for the elliptic curve cryptosystem and are centred around three
areas,
1. Public/Private key pair generation,
2. Encryption
3. Decryption.
3.2.1
Public/Private key pair generation
· FR01: The user will be given a dialogue box containing fields that must be filled in order to generate
a key pair.
· FR02: User must be able to enter a name which will be used to identify the owner of the key pair.
· FR03: User must be able to enter an e-mail address which is also used for identification.
· FR06: The system must store the generated key pair in a secure keyring.
· FR07: The system must allow the user to view the generated key pair.
· FR08: The system must allow the user to import a public key.
· FR09: The system must allow the user to import a private key.
3.2.2
Encryption
· FR11: The system must allow the import of the file to be encrypted. The file will be selected from the
users machine.
· FR12: The system must have a field to allow user fed text to be encrypted instead of an imported file.
· FR13: The system must allow the user to select a target for the message from the current list of public
keys.
· FR14: The system must allow the user to select a key to sign the encrypted file.
· FR16: The system must encrypt and export the resultant file to a location chosen by the user.
3.2.3
Decryption
· FR17: The system must allow the user to import a file to be decrypted.
· FR18: The system must have a field to allow user fed text to be decrypted instead of an imported file.
· FR20: The system must export the resultant file
17
3.3
Non-Functional Requirements
The following are the non-functional requirements for the elliptic curve based cryptosystem.
· NFR01: The system shall be designed using secure coding techniques. This will ensure no vulnerabilities
interfere with the correct functioning of the system whilst also maintaining system integrity
· NFR02: The system shall have a clear and concise user interface, with areas for inputting and viewing
text along with buttons to allow the user to select between generating a key pair and encryption/de-
cryption.
· NFR03: The system shall be built on open source resources and thus be open source itself.
· NFR04: The system should be user friendly and be easily operable. A novice user should be able to
utilise all features with ease.
· NFR05: The system shall be coded using the Java programming language.
18
4
Design
This phase of the document will describe the crypto system in terms of the three main requirements outlined in
section 4 - public/private keypair generation, encryption and decryption. Class diagrams will first be described
followed by sequence diagrams.
4.1
Class Diagrams
The following class diagrams show the Encryption, Decryption, KeyGen and Process Text methods, along
with an overall class structure diagram.
4.1.1
Encrypt Class Diagram
Figure 4: Encrypt Class Diagram
19
4.1.2
Decrypt Class Diagram
Figure 5: Decrypt Class Diagram
20
4.1.3
KeyGen Class Diagram
Figure 6: Key Generation Class
21
4.1.4
Process Text Class Diagram
Figure 7: Encrypt/Decrypt Text
22
4.1.5
Class Structure
Figure 8: Class Structure
23
4.2
Sequence Diagrams
4.2.1
Process Text Sequence Diagram
Figure 9: Process Text Sequence Diagram
24
4.2.2
Encrypt Sequence Diagram
Figure 10: Encrypt Sequence Diagram
25
4.2.3
Decrypt Sequence Diagram
Figure 11: Decrypt Sequence Diagram
26
4.2.4
toHex method Sequence Diagram
Figure 12: toHex Sequence Diagram
27
5
Implementation
5.1
Introduction
This section will detail the methods used to implement the cryptosystem as previously defined - see 3.
Concerning the use of external libraries; It was noted that Java contains very limited native support for
Elliptic Curve Cryptography, thus the decision was made to employ an external library - BouncyCastle -
capable of providing the required features and free from licensing restrictions.
5.2
Week 1
An implementation plan was created. See 1.5.2
5.3
Week 2: Graphical User Interface (GUI)
As per section 3.3, the GUI was created to offer a clear and concise interface for the cryptosystem. Observe
the main screen below:
Figure 13: Main GUI window
As can be seen, there are 7 buttons, each of which corresponds to a unit of functionality as per section
3.2. The Generate Key button provides functionality for the generation of a private\public keypair and when
pressed, opens an additional window to generate and display the keypair.
28
Figure 14: GUI showing the Key-Pair generator with generated keys.
The Process Text button allows the user to encrypt or decrypt text as per section 3.2.2 and is displayed
below.
The encrypt button, provides a means to encrypt a file located in the users hard drive and contains a file
chooser, encrypt button and exit button. See 3.2.2
Figure 15: GUI showing the Encrypt File function
29
The Decrypt File button allows for a previously encrypted file to be decrypted. The user selects the file
from the hard drive. The View Key button allows the user to view the public and private keys along with the
variables used to construct them. See 3.2.1
Figure 16: GUI showing the View Key function
30
5.4
Week 3 - 4: Key Pair Generation
In order to create the EC key pair the chosen curve - see 2.4 - must be defined in Java. A class was created
called 'P384CurveParams' which will be used to code the curve parameters. Observe the following:
Figure 17: Code snippet showing the P384 curve parameters
The figure below shows the values returned by the P384CurveParameters() method:
b y t e [ ]
s e c p 3 8 4 r 1 S e e d = ( Hex . d e c o d e ( " A335926AA319A27A1D00896A6773A4827ACDAC73 " ) ) ;
r e t u r n new X9ECParameters ( s e c p 3 8 4 r 1 C u r v e , s e c p 3 8 4 r 1 B a s e P o i n t , s e c p 3 8 4 r 1 n ,
s e c p 3 8 4 r 1 h , s e c p 3 8 4 r 1 S e e d ) ;
Figure 18: Return values for the P384CurveParameters() method.
Above can be seen the parameters, p, a, b, x, y, n and G(xG, yG), which were documented in 2.4, and
are encoded using the ECFieldElement and ECPoint classes. The classes were imported from the BouncyCastle
Library -
i m p o r t o r g . b o u n c y c a s t l e . a s n 1 . x9 . X9ECParameters ;
i m p o r t o r g . b o u n c y c a s t l e . math . e c . E CP oi nt ;
i m p o r t o r g . b o u n c y c a s t l e . math . e c . ECCurve ;
Figure 19: ECPoint and ECFieldElement classes
31
These parameters were then used to create an X9ECParameters object.
2
The variable domainParams -
an ECDomainParamaters object - is used to create the parameters needed to construct the key pair.
P384CurveParams parms = new P384CurveParams ( ) ;
X9ECParameters e c p = parms . P 3 8 4 c u r v e P a r a m s ( ) ;
domainParams = new
ECDomainParameters ( e c p . g e t C u r v e ( ) , e c p . getG ( ) , e c p . getN ( ) ,
e c p . getH ( ) , e c p . g e t S e e d ( ) ) ;
Figure 20: ECDomainParameters construction.
The ECKeyGenerationParameters object , which will be used to initialise the KeyPairGenerator, is created
in the following fashion -
keyGenParams = new E C K e y G e n e r a t i o n P a r a m e t e r s ( domainParams , new SecureRandom ( ) ) ;
E C K e y P a i r G e n e r a t o r g e n e r a t o r = new E C K e y P a i r G e n e r a t o r ( ) ;
A s y m m e t r i c C i p h e r K e y P a i r k e y P a i r = g e n e r a t o r . g e n e r a t e K e y P a i r ( ) ;
Figure 21: Initialising the KeyPairGenerator
In order to extract the private and public keys from the key pair - remembering from 2.3 that they are
mathematically linked - the following code was used:
p r i v a t e K e y = ( E C P r i v a t e K e y P a r a m e t e r s ) k e y P a i r . g e t P r i v a t e ( ) ;
p u b l i c K e y = ( E C P u b l i c K e y P a r a m e t e r s ) k e y P a i r . g e t P u b l i c ( ) ;
p r i v a t e K e y B y t e s = p r i v a t e K e y . getD ( ) . t o B y t e A r r a y ( ) ;
Figure 22: Private and public key extraction.
The privateKey and publicKey variables are ECPrivateKeyParameters and ECPublicKeyParameters objects
respectively. The need to cast the objects occurs as a result of the method keyPair.getPrivate() which returns
an AsymmetricKeyParameter - a super-class of ECKeyParameters. The following is an example of an Elliptic
Curve Private\Public Key Pair created using the P384 curve:
PRIVATE KEY :
009 b 2 9 7 c 0 1 c e a 9 e 4 3 3 5 8 d 3 9 a 2 9 7 f e e 1 b 7 d 0 7 9 5 a d 8 c 1 4 0 9 8 4 1 a d
32220 b c 5 e 5 4 5 3 9 8 a 2 4 d 5 f 5 2 e d 4 2 9 2 b c 8 b f 0 8 0 9 6 5 3 8 b b d a 2
PUBLIC KEY :
03 c 3 e 2 1 2 d c 8 7 6 9 a 3 7 3 c b 8 d a 0 f 4 d c 5 3 0 2 9 2 1 9 b f c 0 e 1 9 8 b b b 0 e 0 5
e 8 2 1 c 8 8 9 7 1 3 f 6 8 3 2 9 6 6 f b 8 8 f 0 7 7 1 c 5 1 f 9 e b 7 2 c f e 1 2 7 5 9 7 c
Figure 23: Private and Public Key examples.
2
See ANSI X9.622005 - Public Key Cryptography for the Financial Services Industry
32
5.5
Weeks 5 - 7: Encryption
As there is no direct method yet available for Elliptic Curve encryption, an alternate solution was applied.
First a Buffered Block Cipher object was created, this was then used to wrap a Cipher Block Chaining object
with an AES encryption engine. Cipher block chaining is a method of block encryption whereby each block
depends on the Initialisation Vector (IV) - which provides semantic security and is essentially a zombie cipher
block - and the preceding cipher block; each block in the chain is XOR'd with the preceding block and then
encrypted. If a single bit in any block in altered the entire chain will become corrupted and undecipherable.
Figure 24: Cipher Block Chaining
The CBC was implemented in Java as follows:
B u f f e r e d B l o c k C i p h e r b u f f B l o c k C i p h e r = new P a d d e d B u f f e r e d B l o c k C i p h e r ( new
C B C B l o c k C i p h e r ( new AESEngine ( ) ) ) ;
Figure 25: Cipher Block Chaining
The buffBlockCipher variable is now ready to be passed into the encryption engine, which will be an
IESEngine and will be used to wrap the buffBlockCipher with 3 digest algorithms and a key agreement
scheme - Elliptic Curve Diffie-Helman.
I E S E n g i n e e n c r y p t i o n E n g i n e = new I E S E n g i n e ( new ECDHBasicAgreement ( ) ,
new K D F 2 B y t e s G e n e r a t o r ( new SHA512Digest ( ) ) , new HMac( new
SHA512Digest ( ) ) ,
b u f f B l o c k C i p h e r ) ;
Figure 26: Encryption engine
As can be seen above, the buffBlockCipher object is wrapped in a SHA512 initiated Hmac - Hashed
Message Authentication - which is then used to seed a KDF2BytesGenerator - Key derivation function. The
encryption engine is now ready to be initiated. In order to do so, a set of cipher parameters needs to be
defined. The following code creates the derivation and encoding function by using a SHA512 digest.
33
SHA512Digest s h a D e r = new SHA512Digest ( ) ;
b y t e
[ ] d = new b y t e [ 5 1 2 ] ;
s h a D e r . d o F i n a l ( d ,
0 ) ;
SHA512Digest s h a E n c = new SHA512Digest ( ) ;
b y t e
[ ] e = new b y t e [ 5 1 2 ] ;
s h a D e r . d o F i n a l ( e ,
0 ) ;
Figure 27: Derivation and Encoding functions
The cipher parameters are initialised using the derivation and encoding functions along with the mac key
size and cipher key size - which in this case in 256 as we are using AES256.2.3
I E S W i t h C i p h e r P a r a m e t e r s p = new I E S W i t h C i p h e r P a r a m e t e r s ( d , e , 5 1 2 , 2 5 6 ) ;
Figure 28: Cipher Parameters
The encryption engine can now be initialised using the cipher parameters and the private\public key pair:
The boolean variable true is used to denote whether the method is for encryption or decryption.
I E S E n g i n e e n c r y p t i o n E n g i n e . i n i t ( t r u e ,
p r i v a t e K e y , p u b l i c K e y , p ) ;
Figure 29: Initialising the Encryption Engine
The actual encryption can now commence. Firstly, a byte array is created and the clear text file is encoded
therein, then the encryption engine processes the file - the encryption. The resultant byte array is then written
to the file system with the suffix '.enc'.
F i l e I n p u t S t r e a m
f i n = new F i l e I n p u t S t r e a m ( c l e a r T e x t F i l e ) ;
b y t e
[ ]
t o E n c r y p t = new b y t e [ ( i n t ) c l e a r T e x t F i l e . l e n g t h ( ) ] ;
f i n . r e a d ( t o E n c r y p t ) ;
f i n . c l o s e ( ) ;
b y t e
[ ]
p r o c e s s O u t E n c r = e n c r y p t i o n E n g i n e . p r o c e s s B l o c k ( t o E n c r y p t , 0 , t o E n c r y p t . l e n g t h ) ;
f o u t = new F i l e O u t p u t S t r e a m ( c l e a r T e x t F i l e . g e t A b s o l u t e P a t h ( ) + " . e n c " ) ;
f o u t . w r i t e ( p r o c e s s O u t E n c r ) ;
f o u t . f l u s h ( ) ;
f o u t . c l o s e ( ) ;
Figure 30: The file byte array is encrypted and saved to the file system.
34
5.6
Week 8: Decryption
Figure 31: CBC Decryption
The decryption method is almost identical to the encryption method, save for the boolean variable - which
denotes encryption or decryption - in 29.
I E S E n g i n e d e c r y p t i o n E n g i n e . i n i t ( f a l s e ,
p r i v a t e K e y , p u b l i c K e y , p ) ;
Figure 32: Decryption initialiser.
b y t e
[ ] p r o c e s s O u t D e c r y p t = d e c r y p t i o n E n g i n e . p r o c e s s B l o c k ( t o D e c r y p t , 0 , t o D e c r y p t . l e n g t h ) ;
Figure 33: Decrypted byte array.
5.7
Week 9: Key Import/Export
As the method for constructing the key pair relied upon external libraries, the project was beholden to the
restrictions placed by the library authors. These included the non-serialisable nature of the classes that
produced the key pair and the lack of default constructors, additionally the libraries contain no support for a
key store in which to contain the keys, were one able to export them.
. An attempt was made to bypass the restrictions by employing an external library called Kryo. This
library wraps objects in a Kryo object and attempts to export the resultant new object. This method was
successful in exporting the keys and was implemented as follows -
35
p u b l i c b y t e [ ]
s e r i a l i z e ( O b j e c t o b j e c t )
{
t r y
{
B y t e A r r a y O u t p u t S t r e a m s t r e a m = new B y t e A r r a y O u t p u t S t r e a m ( ) ;
// F i l e O u t p u t S t r e a m s t r e a m = new F i l e O u t p u t S t r e a m ( " t e s t " ) ;
Output o u t p u t = new Output ( s t r e a m ) ;
// s t r e a m . f l u s h ( ) ;
// s t r e a m . c l o s e ( )
o u t p u t . c l o s e ( ) ;
r e t u r n s t r e a m . t o B y t e A r r a y ( ) ;
}
c a t c h ( I O E X c e p t i o n i o e x )
{
i o e x . p r i n t S t a c k T r a c e ( ) ;
}
Figure 34: Key import/export attempt
The problem arose, however, during the import stage. As the keys were exported to a byte array, and a
File object, they were imported as one too. Kryo looked for a default constructor with which to create the
imported object and, of coarse, there was none, due to the nature of the key pair - see 5.4
i n K e y = p u b l i c C h o o s e r . g e t S e l e c t e d F i l e ( ) ;
i n p u t = new I n p u t ( new F i l e I n p u t S t r e a m ( i n K e y ) ) ;
p u b l K e y =( c r y p t o . params . E C P u b l i c K e y P a r a m e t e r s ) k r y o P u b l i c . r e a d C l a s s A n d O b j e c t ( i n p u t ) ;
Figure 35: Kryo import method.
36
6
Conclusion
6.1
Evaluation
Currently Elliptic Curve Cryptography is in it's infancy, commercially at any rate, and as such has not had
the wide spread developer attention that RSA enjoys. Internal Java support for ECC is limited at best, so the
decision was made to utilise an external library to provide the necessary support for the project. BouncyCastle
was chosen for two reasons; it was an open source library and it contained all the necessary tools to construct
the cryptosystem. However, it would be preferable for one to construct the libraries from scratch, the reasoning
being that imported libraries are inherently insecure as they were written by, essentially, persons unknown,
and could contain any number of features designed to subvert the security of the system - as was stated in ??
- or allow the writer dangerous knowledge of all cryptosystems developed using the libraries. Developing the
libraries from the ground up would also alleviate the problem of key import and export and would allow the
creation of a dedicated key store in which to securely store them. At present both these features are lacking
in the appropriate available libraries.
Ultimately the project was a success; Elliptic curves were utilised to create a cryptosystem capable of
securely enciphering and deciphering files and text. Best practices were followed according to the NSA's Cryp-
tographic Interoperability Strategy (CIS) or Suite B Cryptography.[National Security Agency(2009)] While a
far cry away from a commercial application, the developed system shows that a viable replacement - Elliptic
Curve Cryptography (ECC) - for RSA is achievable and demonstrably superior in the role - see 2.3
6.2
Further Work
Cryptography's raison d'être, as was shown, is to encipher and decipher information and is traditionally
deployed as a defensive measure, a method to protect and conceal. Consider then an alternate deployment,
where-by cryptography is used as an offensive weapon, a method to effectively hold data for ransom, as was
seen with the Cryptolocker virus, or as an area-denial weapon - a cyber equivalent to an artillery barrage.
Weaponised cryptography has the potential to cause devastating damage to global internet infrastructure.
An attacker could offensively deploy a cryptographic payload to multiple critical internet nodes, encrypting
the entire contents of swaths of the internet which would result not only in loss of data, but would also
see global internet traffic grind to a halt. Thus it is clear that while highly secure cryptographic protocols
are increasingly more desirable, care must be taken to examine the implications of creating such protocols
and conduct research into defensive measures lest they be turned against us; As Dr. Frankenstein lamented
"When I reflected on his crimes and malice, my hatred and revenge burst all bounds of moderation. I would
have made a pilgrimage to the highest peak of the Andes, could I when there have precipitated him to their
base."[Shelly(2007)]
37
References
[ANSI(1998)] ANSI, Jul. 1998. Public key cryptography for the financial services industry: Elliptic curve key
agreement and key transport schemes. Tech. Rep. Version 2.
[Centicom Research(1999)] Centicom Research, Oct. 1999. Recommended elliptic curve domain parameters.
[ElGamal(1985)] ElGamal, T., 1985. A public key cryptosystem and a signature scheme based on discrete
logarithms. IEEE Transactions on Information Theory 31, 469472.
[Gallant et al.(1999)Gallant, Lambert, and Vanstone] Gallant, R., Lambert, R., Vanstone, S., May 1999. Im-
proving the parallelized pollard lambda search on anamalous binary curves. Mathematics of Computation
69 (232), 16991705.
[Guajardo and Paar(1997)] Guajardo, J., Paar, C., 1997. Efficient algorithms for elliptic curve cryptosystems.
Lecture Notes in Computer Science 1294, 342356.
[Hankerson et al.(2000)Hankerson, Hernandez, and Menezes] Hankerson, D., Hernandez, J. L., Menezes, A.,
2000. Software implementation of elliptic curve cryptography over binary fields. Cryptographic Hardware
and Embedded Systems, 124.
[ISO/IEC 15946(1999)] ISO/IEC 15946, 1999. Information technology - security techniques - cryptographic
techniques based on elliptic curves. Committee draft.
[Joye and Tymen(2001)] Joye, M., Tymen, C., 2001. Protections against differential analysis for elliptic curve
cryptography - an algebraic approach. Cryptographic Hardware and Embedded Systems 2162 (Lecture
Notes in Computer Science), 377390.
[Kapoor et al.(2008)Kapoor, Abraham, and Singh] Kapoor, V., Abraham, V. S., Singh, R., May 2008. Elliptic
curve cryptography. ACM Ubiquity 9 (20).
[Koblitz(1987)] Koblitz, N., Jan. 1987. Elliptic curve cryptosytems. Mathematics of Computation 48 (177),
203209.
[Koblitz(1989)] Koblitz, N., 1989. Hyperelliptic cryptosystems. Journal of Cryptology 1, 139150.
[Koblitz(1993)] Koblitz, N., 1993. Introduction to Elliptic Curves and Modular Forms, 2nd Edition. Springer-
Verlag.
[Koblitz et al.(2000)Koblitz, Menezes, and Vanstone] Koblitz, N., Menezes, A., Vanstone, S., 2000. The
state of elliptic curve cryptography. Designs, Codes and Cryptography 19, 173193.
[McGrew et al.(2011)McGrew, Igoe, Salter, Cisco Systems, and National Security Agency] McGrew,
D.,
Igoe, K., Salter, M., Cisco Systems, National Security Agency, Feb. 2011. Fundamental elliptic curve
cryptography algorithms. Tech. Rep. RFC 6090, IETF.
URL http://tools.ietf.org/html/rfc6090
[National Institute of Standards and Technology(2007)] National Institute of Standards and Technology,
Mar. 2007. Recommendation for pair-wise key establishment schemes using discrete logarithm cryp-
tography (revised). Special publication 800-56A.
[National Institute of Standards and Technology(2010)] National Institute of Standards and Technology, Apr.
2010. Mathematical routines fo the NIST prime elliptic curves. Tech. rep., NIST.
URL http://www.nsa.gov/ia/_files/nist-routines.pdf
[National Security Agency(2009)] National Security Agency, 2009. Suite b cryptography.
URL http://www.nsa.gov/ia/programs/suiteb_cryptography/
[Shelly(2007)] Shelly, M., 2007. Frankenstein, illustrated, annotated Edition. Infobase Publishing.
[Thijssen(2010)] Thijssen, J., Dec. 2010. Encryption operating modes: ECB vs CBC.
URL https://www.adayinthelifeof.nl/2010/12/08/encryption-operating-modes-ecb-vs-cbc/
38
Frequently asked questions
What is the primary topic of "Investigation into the Cryptographic Properties of Elliptic Curves Defined over a Prime Field"?
The primary topic is an investigation into elliptic curve cryptography (ECC), including its mathematical properties, its comparison with RSA, the selection of appropriate elliptic curves, and the design of a software system to demonstrate ECC's capabilities.
What are the main objectives of this investigation?
The main objectives are to: Investigate the mathematical properties of elliptic curves as they relate to cryptography; Analyse ECC as an alternate to RSA; Identify and select an appropriate elliptic curve for use in a cryptosystem; Design and develop a cryptographic software system as a vehicle for this investigation.
What are the key themes discussed in the document?
The key themes include: Elliptic curve cryptography (ECC), RSA as a comparison, mathematical construction of elliptic curves, curve parameter selection, software implementation, and a comparison to NSA's Suite B cryptography recommendations.
What is the Discrete Log Problem (DLP) in the context of ECC?
The DLP is the foundation of ECC, expressed as finding an integer 'k' such that Q = kP, where k = logp(Q) and P, Q are points in (Zp).
How does ECC compare to RSA in terms of complexity and resistance to attack?
ECC achieves a greater level of complexity than RSA in terms of resistance to attack, primarily because the DLP is considered harder than the Integer Factorization Problem upon which RSA is based. It requires much smaller keys for the equivalent security level.
What kind of software system will be developed as part of this investigation?
A Java-based system will be developed to enable users to construct an asymmetric cipher key pair based on Elliptic Curves and use those keys to encrypt and decrypt files and text.
Which elliptic curve parameters are considered in the project?
The project considers parameters recommended by NIST, specifically focusing on prime field curves suitable for NSA's Suite B security requirements, especially the P-384 curve.
What external library is used for implementing ECC in Java?
The Bouncy Castle library is used for providing ECC functionality due to Java's limited native support for elliptic curve cryptography.
What encryption scheme is utilized in the software system?
The Elliptic Curve Integrated Encryption Scheme (ECIES) is the encryption scheme utilized in the developed system.
What is the Cipher Block Chaining (CBC) technique used for?
Cipher Block Chaining is used for block encryption to enhance security. Each block depends on the Initialisation Vector (IV) and the preceding cipher block. Meaning, each block in the chain is XOR'd with the preceding block and then encrypted.
Why RSA was excluded from NSA's Cryptographic Interoperability Strategy (CIS) or Suite B Cryptography?
It was explicitly stated that, as the document is only a Language Preview, the reason was not provided, or included in the text. The reader would have to read the full document, or the original source document itself.
What are some of the specific functional requirements of the software system?
Some functional requirements are: Public/Private key pair generation, where users can enter identification information; encryption and decryption of both imported files and user-fed text; secure key ring storage and key viewing; and importing/exporting keys.
What was the conclusion of the investigation?
The final evaluation of the investigation found that ECC was superior in terms of security, in comparison to RSA. It was found to be a viable replacement to RSA.
What are the further works for future development?
The future development recommends that further steps are taken to "examine the implications of creating such protocols" to guard against future attacks.
Excerpt out of 38 pages
- scroll top
- Quote paper
- Adrian O'Gara (Author), 2014, Investigation into the Cryptographic Properties of Elliptic Curves Defined over a Prime Field, Munich, GRIN Verlag, https://www.grin.com/document/295698
Look inside the ebook
