For all of you who are trying to figure out how to integrate with Google’s single sign-on functionality (like I’ve done for my own startup at tripgather.com), this article I published on ocpsoft.org might be for you. I’ve taken the liberty of condensing all of the actual logic required to perform OAuth Google login, and provided it as a class and a JSP. In order to follow along better, I suggest cloning the example GitHub repository, and deploying to the application to your server of choice.

## Generating geolocation data using java and mysql

A few of my projects involved creating a strictly auto-completing textfield based on location data. The autocomplete is reasonably straight forward so I’m leaving that as a casual exercise for the reader. This article presents pointers on where to get geographical information, extract pertinent information, then store that in a mysql table for quick lookup. Having this data helped me answer a multitude of questions, to mention a few:

- What’s the nearest city (of a certain size) to a given geocode?
- Given a geocode, find the timezone. (accuracy depends on the amount of data you wish to store)
- Given a substring, find all cities and/or states whose names contain the substring.
- Find the number of cities in a 25 mile radius around a given geocode.

Let’s jump right in. For my projects I’ll keep track of a few pieces of data using a mysql table:

```
CREATE TABLE `geonames` (
`geonames_id` bigint(20) unsigned NOT NULL auto_increment,
`city_name` varchar(200) NOT NULL default '',
`state_code` varchar(20) NOT NULL default '',
`country_code` varchar(4) NOT NULL default '',
`latitude` float(8,5) NOT NULL,
`longitude` float(8,5) NOT NULL,
`timezone` varchar(200) NOT NULL default '',
`population` int(10) NOT NULL default '0',
PRIMARY KEY (`geonames_id`),
KEY `index1` USING BTREE (`latitude`),
KEY `index2` USING BTREE (`longitude`),
KEY `index3` USING BTREE (`latitude`,`longitude`)
)
```

As you can see, the table keeps track of the city, state, country, latitude, longitude, timezone, and population count of a given location. The table declares BTREE indexes for the latitude-longitude information. This is fine enough for my purposes.

Having this table would be of not much use without the data. Where is it, you ask?

HERE: http://download.geonames.org/export/dump/

For our purposes, I’m using US.zip, and CA.zip. The contents of the zip files contain much more data than we’re interested in. This is where CODING FUN begins.

The following class parses the unpacked US.txt, CA.txt files and transforms them to tab delimited files that then can be manually loaded into mysql.

This code only writes information if it encounters a place with population, and the population is above a certain number. Specifically, it will only pick up places with more than 5000 people.

```
package com.tripgather.util;
import java.io.*;
import java.util.HashMap;
import java.util.logging.Level;
import java.util.logging.Logger;
/**
* This class contains utility methods to parse geonames.org files and transform
* them into something that is selfishly useful.
*
* Please familiarize yourself with GeoNames Feature Codes at:
* http://www.geonames.org/export/codes.html
*
* Data can be downloaded from: http://download.geonames.org/export/dump/
*
* @author mdanter
*/
public class GeonamesTransformer {
/**
* The separator to use for splitting the input and outputting the
* transformed file.
*/
private static final String SEPARATOR_CHAR = "t";
/**
* Designates newline.
*/
private static final String NEWLINE_CHAR = "n";
/**
* Initial size for BufferedWriter, large #s yield better performance.
*/
private static final int BUFFER_SIZE = 99999;
/**
* Determines what size a populated are has to be in order to be output.
*/
private static final int POPULATION_THRESHOLD = 5000;
/**
* The index of the column in the geonames file.
*/
private static final int POPULATION_SIZE = 14;
/**
* The index of the column in the geonames file.
*/
private static final int LOCATION_DESIGNATION = 6;
/**
* The index of the column in the geonames file.
*/
private static final int LOCATION_ID = 0;
/**
* The index of the column in the geonames file.
*/
private static final int LOCATION_CITY = 2;
/**
* The index of the column in the geonames file.
*/
private static final int LOCATION_STATE = 10;
/**
* The index of the column in the geonames file.
*/
private static final int LOCATION_LAT = 4;
/**
* The index of the column in the geonames file.
*/
private static final int LOCATION_LNG = 5;
/**
* The index of the column in the geonames file.
*/
private static final int LOCATION_TZINFO = 17;
/**
* Country code we want to appear in the output for USA.
*/
private static final String COUNTRY_CODE_US = "US";
/**
* Country code we want to appear in the output for Canada.
*/
private static final String COUNTRY_CODE_CA = "CA";
/**
* Used to correlate Canadian province codes with 2 letter acronym.
*/
private static final HashMap< String, String > CANADIAN_PROVINCES = new HashMap< String, String >(13);
static {
CANADIAN_PROVINCES.put("01", "AB");
CANADIAN_PROVINCES.put("02", "BC");
CANADIAN_PROVINCES.put("03", "MB");
CANADIAN_PROVINCES.put("04", "NB");
CANADIAN_PROVINCES.put("05", "NL");
CANADIAN_PROVINCES.put("07", "NS");
CANADIAN_PROVINCES.put("13", "NT");
CANADIAN_PROVINCES.put("14", "NU");
CANADIAN_PROVINCES.put("08", "ON");
CANADIAN_PROVINCES.put("09", "PE");
CANADIAN_PROVINCES.put("10", "QC");
CANADIAN_PROVINCES.put("11", "SK");
CANADIAN_PROVINCES.put("12", "YT");
}
/**
* @param args the command line arguments
*/
public static void main(final String[] args) {
final long start = System.currentTimeMillis();
buildData("/Users/mdanter/Downloads/US/US.txt", "/tmp/dataUS.txt", POPULATION_THRESHOLD, COUNTRY_CODE_US);
buildData("/Users/mdanter/Downloads/CA/CA.txt", "/tmp/dataCA.txt", POPULATION_THRESHOLD, COUNTRY_CODE_CA);
final long end = System.currentTimeMillis();
Logger.getLogger(GeonamesTransformer.class.getName()).log(Level.INFO, "ETL TOOK: " + (end - start) + "ms");
}
/**
* Designed to read an unzipped geonames file and transform it, while
* writing only places with population, and only places that have population
* above a certain size.
*
* @param filePath the path to the input text file obtained from geonames by
* extracting the zip file
* @param outputPath the path to output the transformed text to
* @param populationSize determines whether a place is added to output based
* on its population's size
* @param countryCode used to designate the country, also used for
* designating the special case for CANADA
*/
public static void buildData(final String filePath,
final String outputPath,
final int populationSize, final String countryCode) {
FileWriter fileWriter = null;
BufferedWriter bufferedWriter = null;
InputStream fStream = null;
BufferedReader bufferedReader = null;
try {
// Open the file
fStream = new FileInputStream(filePath);
// Get the object of DataInputStream
bufferedReader = new BufferedReader(new InputStreamReader(fStream));
fileWriter = new FileWriter(outputPath);
bufferedWriter = new BufferedWriter(fileWriter, BUFFER_SIZE);
if (COUNTRY_CODE_CA.equals(countryCode)) {
transformFileForCA(bufferedReader, populationSize, bufferedWriter);
} else {
transformFile(bufferedReader, populationSize, countryCode, bufferedWriter);
}
} catch (Exception e) {//Catch exception if any
Logger.getLogger(GeonamesTransformer.class.getName()).log(Level.SEVERE, e.getMessage());
} finally {
try {
//Close the streams
fStream.close();
bufferedWriter.close();
fileWriter.close();
bufferedReader.close();
} catch (Exception ex) {
Logger.getLogger(GeonamesTransformer.class.getName()).log(Level.SEVERE, ex.getMessage());
}
}
}
/**
* Designed to read an unzipped geonames file and transform it, while
* writing only places with population, and only places that have population
* above a certain size.
*
* @param bufferedReader obtained from geonames file
* @param populationSize determines whether a place is added to output based
* on its population's size
* @param countryCode used to designate the country, also used for
* designating the special case for CANADA
* @param bufferedWriter outputs to file designated for transformed content
* @throws IOException
* @throws NumberFormatException
*/
private static void transformFile(final BufferedReader bufferedReader,
final int populationSize,
final String countryCode,
final BufferedWriter bufferedWriter)
throws IOException, NumberFormatException {
String strLine;
StringBuffer transformedLine;
//Read File Line By Line
while ((strLine = bufferedReader.readLine()) != null) {
// Print the content to file
final String[] cols = strLine.split(SEPARATOR_CHAR);
if ("P".equalsIgnoreCase(cols[LOCATION_DESIGNATION])) {//we're only interested in places
final int population = Integer.parseInt(cols[POPULATION_SIZE]);
if (population > populationSize) {
transformedLine = transformLine(cols, countryCode);
bufferedWriter.write(transformedLine.toString());
}
}
}
}
/**
* Designed to read an unzipped geonames file and transform it, while
* writing only places with population, and only places that have population
* above a certain size, special case for Canada
*
* @param bufferedReader obtained from the geonames file
* @param populationSize determines whether a place is added to output based
* on its population's size
* @param bufferedWriter outputs to file designated for transformed content
* @throws NumberFormatException
* @throws IOException
*/
private static void transformFileForCA(final BufferedReader bufferedReader,
final int populationSize,
final BufferedWriter bufferedWriter)
throws NumberFormatException, IOException {
String strLine;
StringBuffer transformedLine;
//Read File Line By Line
while ((strLine = bufferedReader.readLine()) != null) {
// Print the content to file
final String[] cols = strLine.split(SEPARATOR_CHAR);
if ("P".equalsIgnoreCase(cols[LOCATION_DESIGNATION])) {//we're only interested in places
final int population = Integer.parseInt(cols[POPULATION_SIZE]);
if (population > populationSize) {
transformedLine = transformLineForCA(cols);
bufferedWriter.write(transformedLine.toString());
}
}
}
}
/**
* Builds a line of output for Canada, this is a special case since we need
* to correlate the numeric provinces with the 2 letter abbreviations for
* familiarity.
*
* @param cols one line of the input geonames file split by t
* @return output line of the transformed String wrapped in Stringbuffer
*/
private static StringBuffer transformLineForCA(final String[] cols) {
final StringBuffer transformedLine = new StringBuffer();
transformedLine.append(cols[LOCATION_ID]).
append(SEPARATOR_CHAR).
append(cols[LOCATION_CITY]).
append(SEPARATOR_CHAR).
append(CANADIAN_PROVINCES.get(cols[LOCATION_STATE])).
append(SEPARATOR_CHAR).
append(COUNTRY_CODE_CA).
append(SEPARATOR_CHAR).
append(cols[LOCATION_LAT]).
append(SEPARATOR_CHAR).
append(cols[LOCATION_LNG]).
append(SEPARATOR_CHAR).
append(cols[LOCATION_TZINFO]).
append(SEPARATOR_CHAR).
append(cols[POPULATION_SIZE]).
append(NEWLINE_CHAR);
return transformedLine;
}
/**
* Generically builds a line of output.
*
* @param cols one line of the input geonames file split by t
* @param countryCode the country code that is desired in the output
* @return output line of the transformed String wrapped in Stringbuffer
*/
private static StringBuffer transformLine(final String[] cols,
final String countryCode) {
final StringBuffer transformedLine = new StringBuffer();
transformedLine.append(cols[LOCATION_ID]).
append(SEPARATOR_CHAR).
append(cols[LOCATION_CITY]).
append(SEPARATOR_CHAR).
append(cols[LOCATION_STATE]).
append(SEPARATOR_CHAR).
append(countryCode).
append(SEPARATOR_CHAR).
append(cols[LOCATION_LAT]).
append(SEPARATOR_CHAR).
append(cols[LOCATION_LNG]).
append(SEPARATOR_CHAR).
append(cols[LOCATION_TZINFO]).
append(SEPARATOR_CHAR).
append(cols[POPULATION_SIZE]).
append(NEWLINE_CHAR);
return transformedLine;
}
}
```

After running the class, there should be two files in /tmp, dataUS.txt, dataCa.txt. These are the files to load into the geonames table using the following SQL statement:

```
LOAD DATA INFILE '/tmp/dataCA.txt' INTO TABLE geonames;
LOAD DATA INFILE '/tmp/dataUS.txt' INTO TABLE geonames;
```

At this point, we are ready to grab some intel based on the newly available data.

Examples:

GET TIMEZONE INFO BY LAT/LNG:

Where the bound parameters are called ?lat and ?lng, I used this in a native query using JPA.

```
SELECT
timezone
FROM (
(SELECT
*,ABS(latitude-?lat) latd, ABS(longitude - ?lng) lngd
FROM
geonames
WHERE
latitude< =?lat AND
longitude<=?lng
ORDER BY latd ASC, lngd ASC
LIMIT 0,1)
UNION
(SELECT
*,ABS(latitude-?lat) latd, ABS(longitude - ?lng) lngd
FROM
geonames
WHERE
latitude>=?lat AND longitude>=?lng
ORDER BY latd ASC, lngd ASC
LIMIT 0,1)
) Tb1
ORDER BY Tb1.lngd ASC
LIMIT 0,1;
```

Would you like to find the nearest area with population above 5000 people? Add fields to the outer most SELECT statement.

GET CITIES BY SUBSTRING:

```
SELECT
CONCAT(city_name,', ',state_code) as location
FROM
geonames
WHERE
city_name like '%needle%'
GROUP BY
city_name, state_code
ORDER BY
population DESC;
```

If you followed this article, you should have a table with useful data, and have basic ideas about how to use it.

## openstreetmap json geolocation using java

A viable free alternative to google’s geolocation api is openstreetmap’s nominatim functionality. The service recommends restricting the frequency of requests to 1 per second, so if nothing else, this is a viable failover alternative to google’s geolocation api.

The code below may be used to query openstreetmap’s nominatim database for latitude/longitude information. It uses the jackson library for json parsing.

If you are using maven, add:

<dependency> <groupId>org.codehaus.jackson</groupId> <artifactId>jackson-jaxrs</artifactId> <version>1.9.4</version> </dependency>

to your pom.xml file’s dependencies to satisfy the import statements in the class below.

```
import java.io.IOException;
import java.io.InputStream;
import java.net.URL;
import java.net.URLEncoder;
import java.util.List;
import java.util.Map;
import java.util.logging.Level;
import java.util.logging.Logger;
import org.codehaus.jackson.map.ObjectMapper;
public class OpenStreetMapGeoCodeJacksonParser {
private static final String LATITUDE = "lat";
private static final String LONGITUDE = "lon";
public LatLng parse(final InputStream jsonStream) {
LatLng coordinate = null;
final ObjectMapper mapper = new ObjectMapper();
try {
final List<Object> dealData = mapper.readValue(jsonStream, List.class);
if (dealData != null && dealData.size() == 1) {
final Map< String, Object > locationMap = (Map< String, Object >) dealData.get(0);
if (locationMap != null && locationMap.containsKey(LATITUDE) && locationMap.containsKey(LONGITUDE)) {
final double lat = Double.parseDouble(locationMap.get(LATITUDE).toString());
final double lng = Double.parseDouble(locationMap.get(LONGITUDE).toString());
coordinate = new LatLng(lat, lng);
}
} else {
Logger.getLogger(OpenStreetMapGeoCodeJacksonParser.class.getName()).log(Level.SEVERE, "NO RESULTS", "NO RESULTS");
}
} catch (Exception ex) {
Logger.getLogger(OpenStreetMapGeoCodeJacksonParser.class.getName()).log(Level.SEVERE, ex.getMessage(), ex);
}
return coordinate;
}
public LatLng parse(String rawAddress) {
InputStream is = null;
LatLng coords = null;
if (rawAddress != null && rawAddress.length() > 0 ) {
try {
String address = URLEncoder.encode(rawAddress, "utf-8");
String geocodeURL = "http://nominatim.openstreetmap.org/search?format=json&limit=1&polygon=0&addressdetails=0&email=contact@EMAIL.ME&countrycodes=us&q=";
//query google geocode api
String formattedUrl = geocodeURL + address;
URL geocodeUrl = new URL(formattedUrl);
is = geocodeUrl.openStream();
coords = parse(is);
} catch (IOException ex) {
Logger.getLogger(OpenStreetMapGeoCodeJacksonParser.class.getName()).log(Level.SEVERE, null, ex);
} finally {
try {
is.close();
} catch (IOException ex) {
Logger.getLogger(OpenStreetMapGeoCodeJacksonParser.class.getName()).log(Level.SEVERE, null, ex);
}
}
}
return coords;
}
public static void main(final String[] args) {
final String rawAddress = "Los Angeles, CA";
System.out.println(new OpenStreetMapGeoCodeJacksonParser().parse(rawAddress));
}
}
```

Please make sure to substitute a valid email address into the geocodeURL’s email GET parameter.

Finally, the LatLng.java class holds the latitude-longitude information.

```
import java.io.Serializable;
/**
*
* @author mdanter
*/
public class LatLng implements Serializable{
private static final long serialVersionUID = 16549987563L;
private double lat;
private double lng;
public LatLng(final double lat, final double lng) {
this.lat = lat;
this.lng = lng;
}
public double getLat() {
return lat;
}
public void setLat(final double lat) {
this.lat = lat;
}
public double getLng() {
return lng;
}
public void setLng(final double lng) {
this.lng = lng;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final LatLng other = (LatLng) obj;
if (Double.doubleToLongBits(this.lat) != Double.doubleToLongBits(other.lat)) {
return false;
}
if (Double.doubleToLongBits(this.lng) != Double.doubleToLongBits(other.lng)) {
return false;
}
return true;
}
@Override
public int hashCode() {
int hash = 3;
hash = 53 * hash + (int) (Double.doubleToLongBits(this.lat) ^ (Double.doubleToLongBits(this.lat) >>> 32));
hash = 53 * hash + (int) (Double.doubleToLongBits(this.lng) ^ (Double.doubleToLongBits(this.lng) >>> 32));
return hash;
}
}
```

## Oracle Glassfish 3.x issue in EJB 3.1 with @Asynchronous methods

Recently, as a pet project, I’ve been working on an application that uses the @Asynchronous method level annotation in a Singleton EJB as per the EJB 3.1 specification. The application consisted of a call to a restful URI, to capture an xml representation of an object, converting this into a POJO (Serializable) then sending it to a MessageQueue as an ObjectMessage. Each datum was independent, and there was a high volume of data to process, I decided to implement the new method level @Asynchronous annotation, the fire-and-forget way. I also built an MDB as a consumer of the Queue, that is however irrelevant to the issue.

Of course this EJB 3.1 application had to be load tested for large volumes of sample data. I’ve made up a test sample that was representative of the projected volume of data, and set the @Asynchronous method’s Thread.sleep() for 5 seconds. The reason for this was to estimate a worst case scenario for the Request-Response lifecycle. The app was deployed into Oracle Glassfish 3.1.1 with tuned EJB and MDB pools, and a somewhat starved 768MB max heap.

While watching the log output, I noticed that the @Asynchronous threads were spawned by bunches of 16. I tried to further tune EJB Thread pools inside of Glassfish — with no luck.

I found the issue on the Glassfish website after checking out the current stable codebase from their subversion repository. In Oracle Glassfish 3.1.1, according to the EjbAsyncInvocationManager.java class in com.sun.ejb.containers the 16 thread limit is hard-coded.

public EjbAsyncInvocationManager() { //TODO get the paramters from ejb-container config super(16, 32, 60, TimeUnit.SECONDS, new LinkedBlockingQueue()); super.setThreadFactory(new EjbAsyncThreadFactory()); }

I’ve checked out the latest stable glassfish (Maven is great, isn’t it?) project, then as a duck tape solution, increased this number to satisfy my application’s needs. As soon as I have time to devote to this issue, I’ll investigate what the best way to fix this would be. I think the least impact to the codebase would be to include the settings for min-max thread-pool size and timeout values in glassfish-ejb-jar.xml somehow nested in the definition for an EJB.

## Serving up Glassfish 3.x from port 80/443 via NAT

After a good amount of load testing and tinkering, I’ve found that mod_jk does not play too well with oracle glassfish 3, at least not in the environment/configuration I’m using. After about 30% of requests timing out in a web app which was using JSF 2 (facelets core, tomahawk, and primefaces) / EJB 3.1 / JPA 2 on top of oracle 11g db (tuned caching, native queries, etc…), the culprit turned out to be mod_jk misbehaving. After diagnosing the issue, I’ve decided to leave the httpd< -->mod_jk< -->glassfish setup behind, and KISS.

I’ve turned off httpd, forwarded all requests using NAT in iptables (just tcp, didn’t need udp, but NAT-ing udp as well doesn’t hurt anything) from port 80 to the port I’ve configured the glassfish http listener to listen on (standard is 8080, probably not a bad idea to change this and NAT to that port). Of course, the glassfish http listener’s port had to be configured to accept connections via iptables.

Glassfish uses grizzly as an http server (impl. uses java NIO under the hood), after performance testing and tuning this a bit… viola, timed out requests gone. With a bit more tuning, of JVM params, resource pool sizes, listener threads, application profiling/monitoring, etc., the app server became much snappier at serving requests. ) you may run two separate domains for glassfish with a more imaginative listener configuration.

Sample commands to achieve NAT using iptables for CentOS/RHEL 5.x:

# iptables -A PREROUTING -t nat -i eth0 -p tcp --dport 80 -j REDIRECT --to-port 8080

# iptables -A PREROUTING -t nat -i eth0 -p udp --dport 80 -j REDIRECT --to-port 8080

```
```

`# service iptables save`

# vi /etc/sysconfig/iptables

-A RH-Firewall-1-INPUT -p tcp -m state --state NEW -m tcp --dport 8080 -j ACCEPT

# service iptables restart

Similarly, you may replace 80 with 443 and 8080 with 8181 to NAT https.

## Elliptic Curve PHP-OOP DSA and Diffie-Hellman

Abstract

Elliptic curves (EC) are smooth algebraic curves of abelian variety, which form a commutative group using the multiplication operation. Elliptic curves may be defined over a variety of fields, for example ℝ, ℂ, ℚ, finite fields, and others. Elliptic curve< cryptography (ECC) is a flavor of public-key cryptography based on elliptic curves over finite fields. This paper provides an introduction to elliptic curves, the elliptic curve digital signature algorithm (ECDSA), and the elliptic curve Diffie-Hellman (ECDH) key agreement scheme. Descriptions of possible attack methods are briefly discussed for EC- based cryptographic schemes. This paper provides an extensive description of a PHP-OOP implementation of ECDSA, and ECDH, based on an implementation of EC using two major multi-precision mathematics extensions (gmp and bcmath) available to PHP.

### 1 Introduction

This paper describes an implementation of elliptic curves and two crypto-schemes based on elliptic curves defined over finite fields of prime modulus in object oriented PHP (PHP-OOP). The implementation leverages the object- oriented syntax of PHP to clearly delineate collections of properties and operations on them. The two crypto schemes discussed in this paper and implemented are the Digital Signature Algorithm (DSA), and the Diffie-Hellman key agreement protocol(DH).

Both protocols rely on public-key cryptography which makes use of asymmetric key algorithms. Asymmetric key algorithms rely on nontrivially related key pairs, a secret private key and a public key. The DSA is a United States Federal Government Standard (FIPS) for digital signatures. The DSA was proposed by the NIST in 1991 and adopted two years later. In order to implement DSA, hashing and public-key cryptography are used. The Diffie-Hellman Key Agreement or Key Exchange protocol is a specific method of exchanging keys and establishing a shared secret over an insecure communication infrastructure. This scheme is one of the earliest practical example of cryptographic key exchange. This protocol was invented and published in 1976 by Whitfield Diffie and Martin Hellman. This key

agreement protocol makes use of public key cryptography which relies on asymmetric key algorithms.[Wade Trappe(2006)]

PHP is a language that is a popular choice for creating web applications, though it may be used for command line script development. PHP was created in 1995, and is a loosely and dynamically typed imperative language that borrows most of its syntax from C, or C++ in the case of object oriented programming. As of the writing of this paper PHP offers two mainstream multi precision mathematics extensions: GMP and bcmath. GMP stands for GNU Multiple Precision arithmetic library. This library is freely available under the GNU general public license, and is optimized for performance. Bcmath received its name from Binary Calculator which supports numbers of any size and precision, represented as strings, this implementation is PHP- specific and does not rely on an underlying system library.[Zandstra(2008)]

Section 2 of this paper provides an introduction to elliptic curves, by describing the operations and related definitions along with a brief description of hashing functions. The elliptic curve variation of public- key cryptography as it applies to DSA is described in Section 3. Section 4 describes the Diffie-Hellman key agreement protocol using elliptic curve asymmetric key algorithms. Implementation details of elliptic curves and the two crypto schemes in PHP-OOP can be found in Section 5.

Due to their cryptographic strength and compactness of the key used for them in comparison to RSA, elliptic curves are naturally applicable to domains of technology where quick computation and limited resources are available. Methods for establishing a secure shared key and verifying authenticity using ECDSA and ECDH, as applied to the web application domain are discussed in Section 6.

### 2 Elliptic Curves Over Finite Fields

Elliptic curves are smooth (continuously differentiable) curves of the form

In the real number system, the equation above may take two shapes depending on how many real roots it has. Please refer to figures 1 and 2 for the graphs with one and three roots. By the nature of elliptic curves we also include a point at ∞ (sometimes called O for order of the curve). This point is usually placed at ±y because the bottom of the y axis is identified with the top.

There is one operation defined on elliptic curves: addition. Addition on elliptic curves differs from adding points in the plane.

The law of addition on an elliptic curve is represented in Figure 3.[Washington(2003)]

Elliptic Curve Addition Law

Let an elliptic curve E be given by y^{2} = x^{3} + bx + c and P_{1} = (x1,y1) and P_{2} = (x2,y2).

First, compute the slope of the tangent line m between P_{1} and P_{2} by:

We find P_{1} + P_{2} = P_{3} = (x_{3},y_{3})

This addition law is associative and commutative, i.e.:

and

Integer multiplication is defined as:

Additionally, elliptic curves hold identities:

This means that ∞ is the additive identity. Thus, P + ∞ = P.

Elliptic curve cryptography is defined on fields with finitely many elements (finite fields) (mod p) where p is a prime number, instead of being defined on ℝ.

The computations above are still used, but division is replaced by finding the multiplicative inverse of the divisor (mod p), that is a∕b = a * b^{-1} where b^{-1} is given by b * b^{-1} = 1(mod p). This requires that p be a prime number so that gcd(b,p) = 1.

An elliptic curve (mod n), where n is a prime number, contains approximately (n + 1) points (that is n points + the additive identity ∞).[Darrel Hankerson(2004)]

A more precise estimate was given by H. Hasse in the 1930s.

Hasse’s theorem

Suppose E(mod p) has N points. Then

The advantage Elliptic Curves lend to cryptography is that there is no good way to attack the elliptic curve analogous discrete logarithm problem.[Wade Trappe(2006)]

Discrete logarithm problem for elliptic curves

Suppose there exist two points P_{1} and P_{2} on a curve C and

The objective is to find a suitable k.

There is no good attack method for the discrete logarithm problem for elliptic curves and other frequently used attack methods, such as the Pohlig-Hellman and Baby step Giant Step attacks work in special situations only, the index calculus attack becomes meaningless for the elliptic curve discrete logarithm problem.

Based on the cryptographically strong property of the discrete logarithm problem above, elliptic curves are good candidates for applications in cryptography. Elliptic curves lend themselves to well known and widely used algorithms in encryption schemes that use public-key cryptography. Two examples are the Digital Signature Algorithm (DSA) and various key agreement protocols such as the Diffie-Hellman key agreement protocol(DH).[Wade Trappe(2006)]

### 3 Digital Signature Algorithm and Elliptic Curves

As with any DSA algorithm, the Elliptic Curve Digital Signature Algorithm (ECDSA), as any DSA algorithm consists of key generation, signing, and verification. The key generation phase consists of two main phases. Phase 1 deals with choosing a hashing function and establishing the parameters that are publicly shared, while the second phase generates a public- private key pair.[I. Blake(1999)]

A cryptographic hash function is a function that takes any data and returns a fixed- size piece of information. Usually, well described methods are used to digest an arbitrary bit string. Hashing functions are commonly chosen to decrease the possibility of arriving at the same fixed size hash from processing two pieces of data that are not initially identical. A common class of deterministic functions for generating hashes are one-way trapdoor functions. One- way trapdoor functions are desirable because, while it is computationally trivial to generate a hash, once it is computed the message may only be verified by re-applying the same function to the original piece of data. This is in most cases achieved by optimizing the loss of information the data incurs while decreasing possible collisions. The situation where the different pieces of input generate the same hash is called a collision. A one-way function must have well documented properties in order to be called a cryptographic hash function. One of these is collision resistance.[Wade Trappe(2006)] Currently the most popular cryptographic hash functions belong in the SHA -1/256/224/512 family. With the exception of SHA-1, the number postfix designates the output size the cryptographic hashing function produces in bits, while SHA-1 produces 160 bit output. In the DSA key generation phase, after choosing a good candidate for a cryptographic hash function, establishing the publicly shared pieces of information will make it possible to verify the signature. When phase 1 is complete a public private key pair must be generated. This is classically carried out by using public key cryptography. Public key cryptography is also referred to as asymmetric key cryptography. Asymmetric key cryptography uses two distinct keys, one for encrypting the data, and another for decrypting it. As opposed to symmetric key cryptography the same key is used for both encryption and decryption. The most notorious asymmetric key cryptographic algorithm is RSA. This section discusses signature generation, signing and signature verification where elliptic curves are used to generate a public-private key pair in a way that is analogous to DSA.

#### 3.1 Signature Generation Algorithm

For Alice (A) to sign and send a message to Bob (B), they must agree upon the field size, the parameters a and b that are the coefficients in y^{2} = x^{3} + ax + b, and base (generator) point G of prime order n. She also must choose d_{A} such that d_{A} ϵ[1,n - 1], and a public key Q_{A} where Q_{A} = d_{A}G.[Wade Trappe(2006)]

Signature Generation Algorithm

In order to sign a message m, Alice follows the algorithm below:

1. Calculate e = HASH(m), where HASH(m) is an arbitrary cryptographically secure hash function.

2. Let l_{0} be the leftmost bit of e.

3. Select a random integer k so that k ϵ[1,n - 1].

4. Calculate r = x_{1}(mod n) where (x_{1},y_{1}) = kG. If r = 0 go back to step 3.

5. Calculate s = k^{-1}(l_{0} + rd_{A})(mod n) . If s = 0 go back to step 3.

6. The signature is (r,s).

Signature Verification Algorithm

In order for Bob (B) to successfully verify Alice’s signature he must have a copy of Q_{A}, which is

Alice’s public key. To verify the authenticity of Q_{A} before verifying the signature, he may check

three conditions:

1. Q_{A}≠O where O is the identity element.

2. the curve contains Q_{A}.

3. nQ_{A} = O.

Now to verify the signature:

1. Verify that r,sϵℤ and r,sϵ[1,n - 1].

2. Calculate e = HASH(m), where the hash function is identical to the one Alice

used.

3. Let l_{0} be the leftmost bit of e.

4. Calculate w = s^{-1}(mod n).

5. Calculate u_{1} = l_{0}w(mod n) and u_{2} = rw(mod n).

6. Calculate (x_{1},y_{1}) = u_{1}G + u_{2}Q_{A}.

7. The signature is valid if r = x_{1}(mod n), invalid otherwise.

#### 3.2 Correctness for ECDSA

Suppose a signature (r,s) on the message m is generated by Alice. Then it follows that

s = k^{-1}(HASH(m) + d_{A}r)(mod n). Thus

kG | = s^{-1}(HASH(m) + d_{A}r)G(mod n) |

= s^{-1}HASH(m)G + s^{-1}rd_{A}G(mod n) |

= HASH(m)wG + rwQ(mod n) |

= u_{1}G + u_{2}Q(mod n) |

Since u_{1}G + u_{2}Q = u_{1}G + u_{2}d_{A}G = (u_{1} + u_{2}d_{A})G = kG, this verifies x_{1} = r as required by DSA.

The main difference of ECDSA from classical DSA is the use of a different asymmetric key algorithm. Classically, the asymmetric key algorithm for signing and verification uses the usual version of the discrete logarithm problem instead of EC version.

### 4 Diffie Hellman Key Agreement

The Diffie-Hellman key agreement protocol is a protocol that allows two parties, each having a public-private key pair, to establish a shared secret over an untrusted or insecure communication channel. For the Elliptic Curve Diffie-Hellman (ECDH) protocol, the public-private key pairs consist of elliptic curves instead of the classical public key generation scheme using discrete logarithms.[Darrel Hankerson(2004)]

Key Establishment Protocol

In order for Alice and Bob to establish a shared key, the two parties must agree on the domain parameters, p that defines the prime field, the coefficients a,b in y^{2} = x^{3} + ax + b, the generator point G, n ϵℤ such that nG = O, and the cofactor h.

■ Alice picks d_{A} randomly such that d_{A} ϵℤ and d_{A} ϵ[1,n - 1]

■ Alice computes Q_{A} = d_{A}G, publishes Q_{A} and keeps d_{A} safe

Similarly

■ Bob picks d_{B} randomly such that d_{B} ϵℤ and d_{B} ϵ[1,n - 1]

■ Alice computes Q_{B} = d_{B}G, publishes Q_{B} and keeps d_{B} safe

Alice computes

Bob

computes

Alice and Bob’s shared key is x_{k}.

d_{B}Q_{A} = d_{A}Q_{B} because d_{A}Q_{B} = d_{A}d_{B}G = d_{B}d_{A}G = d_{B}Q_{A}

The Diffie-Hellman key agreement protocol is secure, because only the public keys (Q_{A,B}) are disclosed. Alice’s ability to derive Bob’s private key is analogous to solving the Elliptic Curve Discreet Logarithm Problem.

### 5 Elliptic Curve Cryptography PHP-OOP API

The PHP-OOP ECC library implementation consists of:

■ interfaces

■ implementing classes

■ a test suite designed to test conformance to ECDSAVS 186, and to demonstrate

usage[Brassham(2004)]

■ necessary utilities for computations

■ index file taking care off class autoloading and initial environment setup in terms of setting

script timeout and allowed memory limits.

The PHP-OOP ECC API was implemented to use one of the two main PHP multi precision math librarary extensions: gmp and bcmath. The implementation is set to evaluate which multi precision mathematics library is present and use the one present for ECC calculations for ECDSA and ECDH. If both gmp and bcmath are present, the implementation favors gmp for performance reasons. For performance statistics and hardware descriptions, please refer to Appendices A, B, C. Look at the bottom of this post to download the source code and the pdf version of this post.

#### 5.1 Elliptic Curve PHP Classes

Let us begin by enumerating the interfaces that the implemented source code adheres to.

The interfaces are:

∙ CurveFpInterface represents an elliptic curve and all operations on it in a prime field.

∙ PointInterface represents a point and all possible operations on it.

For the interface source code please refer to the bottom links in this post.

The implementation of the interfaces listed above is in the classes directory at the same level as the interface directory.

The files responsible for basic elliptic curve arithmetic and supporting operations are CurveFp.php, Point.php, NumberTheory.php, gmp_Utils.php, and bcmath_Utils.php. The methods in CurveFp.php, Point.php, NumberTheory.php contain source code implements

operations using both bcmath and gmp, or reports an exception if neither multi precision mathematics library is present.

##### 5.1.1 NumberTheory.php

This class encapsulates static methods that are concerned with computing number theoretic algorithms. The most used static methods in this class are is_prime(p), next_prime(p), and inverse_mod(a, m). the method inverse_mod is the most frequently used method and it is also the most costly in the case of bcmath, as that library has no native implementation for computing multiplicative inverses in a prime field. In the case of gmp, this operation is supported in the extension’s API.

##### 5.1.2 gmp_Utils.php

This class encapsulates static methods that are needed for elliptic curve arithmetic for the implementation using the gmp library extension, namely modular arithmetic and pseudo- random number generation. Note: The method gmp_mod2 had to be constructed in order to repair a bug with modular arithmetic in PHP’s gmp extension. This bug may be architecture dependent.

##### 5.1.3 bcmath_Utils.php

This class encapsulates static methods that are needed for elliptic curve arithmetic for the implementation using the bcmath library extension, namely random number generation, bitwise operations, and number base conversions.

##### 5.1.4 CurveFp.php

The CurveFp class represents an elliptic curve over a prime field. In addition to storing the coefficients a,b and the base prime, this class verifies point containment on its instance using the contains public function, and contains a static method for comparing two CurveFp instances.

This method tests if the point (x,y) is contained on the curve of an instantiated CurveFp object.

The method uses the line

gmp_cmp ( gmp_Utils::gmp_mod2 ( gmp_sub ( gmp_pow(y, 2), gmp_add ( gmp_add ( gmp_pow(x, 3), gmp_mul(this->a, x) ), this->b ) ), this->prime ), 0 )

which translates to the logical comparison

which is derived from

If

RHS = LHS, the current CurveFp object contains (x,y).

This static method compares cp1 and cp2 CurveFp instance variables to decide whether cp1 is identical to cp2.

##### 5.1.5 Point.php

The Point class encapsulates all operations on a point on an elliptic curve. A point references a CurveFp object an (x,y) coordinate, and order associated with a point. Infinity is represented using a static variable named infinity.

The Point constructor’s purpose is to check whether a point is contained on the curve that the Point object was instantiated with, and check that the order multiplied by the point results in the additive identity O if the order of a point was supplied.

This static method’s purpose is to compare two points. Point equality means that both x1 and x2 are of type Point; moreover, x1’s values match x2’s values along with their CurveFp values as demonstrated below.

if ((x1->x == x2->x) && (x1->y == x2->y) && CurveFp::cmp(x1->curve, x2->curve)) { return 0; } else { return 1; }

The three methods below are of key importance for elliptic curve arithmetic. By the nature of elliptic curve arithmetic, integer multiplication of a point means

where k ϵℤ.

Elliptic curve multiplication takes place in mul using the double, add, and leftmost_bit static methods.

add expects two point instances p_{1} and p_{2} as inputs.

p_{1} = (x_{1},y_{1}), p_{2} = (x_{2},y_{x})

point addition algorithm

The algorithm below implements elliptic curve point addition where P_{1}≠ P_{2}

if (the curve for p1 matches the curve for p2) { if (x1 = x2 mod p) { //at this point the y values may either be identical or opposite in sign if (y1=-y2 mod p) { return infinity } else { //call double instead of add return double } } //if x1 != x2 p = p1->curve->getPrime(); //compute the slope according to the formula where P1 != P2 l = (p2->y - p1->y) * inverse_mod(p2->x - p1->x, p); x3 = (l^2 - p1->x - p2->x) mod p; y3 = (l * (p1->x - x3) - p1->y) mod p; p3 = new Point(x1->curve, x3, y3); return p3; } else { //The Elliptic Curves do not match }

double expects two point instances p_{1} and p_{2} as inputs.

p_{1} = (x_{1},y_{1}), p_{2} = (x_{2},y_{x})

point doubling algorithm

The algorithm below implements elliptic curve point doubling i.e.(P_{1}= P_{2})

//p is the curve’s prime base //a is p1’s a coefficient //l is the slope inverse = inverse_mod((2 * p1->y), p); three_x2 = 3 * ($p1->x^ 2); l = ((three_x2 + a) * inverse) mod p; x3 = ((l^2) - (2 * p1->x)) mod p; y3 = ((l * (p1->x - x3)) - p1->y) mod p; if (0 > y3) y3 = p + y3; p3 = new Point(p1->curve, x3, y3); return p3;

The point multiplication algorithm

This is the classical double-and-add algorithm. The double-and-add method using k * P where k ϵℤ and P a point on an elliptic curve consists of decomposing k such that k = k_{0} + 2k_{1} + 2^{2}k_{2} + … + 2^{j}k_{j}. Classically, the double-and-add method may be described as

P a point Q a point, the result of k*P k element of Z Q=P for i from j to 0 do Q = 2Q //double Q if k_i = 1 then Q := Q+P return Q

This algorithm is modified below to account for positive and negative y values during scalar multiplication.

e = k; if (cmp(p1, infinity) == 0) { return infinity } if (p1->order != null) { e = e mod p1->order } if (e == 0) { return infinity } if (e > 0) { e3 = 3 * e negative_self = new Point(p1->curve, p1->x, - p1->y, p1->order) i = leftmost_bit(e3) / 2 result = p1 while (i > 1) { result = double(result) if ( (e3 & i) != 0 && (e & i) == 0) { result = add(result, p1) } if ((e3 & i) == 0 && (e & i) != 0) { result = add(result, negative_self) } i = (i / 2) } } return result

During each iteration in the scalar multiplication algorithm, this method is used to determine whether double, or double-and-add is performed.

if (x > 0) { result = 1; while (result <= x ) { result = 2 * result; } return result/2; }

#### 5.2 Elliptic Curve Digital Signature Algorithm

∙ PrivateKeyInterface represents signature generation for ECDSA.

∙ PublicKeyInterface represents signature verification for ECDSA.

∙ SignatureInterface represents signature pair encapsulation for ECDSA.

##### 5.2.1 PrivateKey.php

The PrivateKey class implements all necessary operations for signature generation. For a reference on the ECDSA algorithm please refer to Section 2.

Constructor

A PrivateKey instance requires the PublicKey, which is a point on an elliptic curve, and a secret (a randomly selected integer mod n).

ECDSA Message Signing

The algorithm of sign adheres to the one in Section 2. Upon successfully signing a hash a new Signature object is returned.

public function sign(hash, random_k) { G = this->public_key->getGenerator() n = G->getOrder() k = random_k mod n p1 = Point::mul(k, G) r = p1->getX() if (r == 0) { report error random number r = 0 } s = mod((inverse_mod(k, n) * mod((hash + (this->secret_multiplier * r)), n)), n) if (s == 0) { report error random number s = 0 } return new Signature(r, s) }

Hashing Function for the Message Digest Stage of ECDSA ECDSA typically uses SHA1 for digesting a message, but other one-way functions may be used.

public static function digest_integer(m) {

return string_to_int(hash(’sha1’, self::int_to_string(m)))

}

Checking point validity

Section 2.1 discusses checking point validity to determine the authenticity of the signature. The algorithm implements the 3 conditions for authenticity checking.

public static function point_is_valid(Point generator, x, y) { n = generator->getOrder(); curve = generator->getCurve(); if (x < 0 || n <= x || y < 0 || n < y <= 0) return false containment = curve->contains(x, y) if (!containment) return false point = new Point(curve, x, y) op = Point::mul(n, point) if (!(Point::cmp(op, Point::infinity) == 0)) return false return true

String to Integer Conversion

The helper functions below are necessary for message digestion. The purpose of the methods is to compute the integer representation of an ASCII string, and vice-versa. Please refer to Appendix D for implementation.

public static function int_to_string(x)

public static function string_to_int(x)

##### 5.2.2 PublicKey.php

The PublicKey class implements all necessary operations for signature verification. For a reference on the ECDSA algorithm please refer to Section 2.

Constructor

A PublicKey instance requires a generator point to access the order of the generator and the public key which is a point on an elliptic curve.

ECDSA Message Verification

The algorithm of verifies adheres to the one in Section 2.1. Upon verification a boolean value is returned based on the validity of the signature.

public function verifies(hash, Signature signature) { G = this->generator; n = this->generator->getOrder(); point = this->point; r = signature->getR(); s =signature->getS(); if (r < 1|| r > (n - 1))) return false if (s < 1 || s > (n - 1)) return false c = inverse_mod(s, n) u1 = hash *c mod n u2 = r * c mod n xy = Point::add(Point::mul(u1, G), Point::mul(u2, point)) v = xy->getX() mod n if (v == r) return true else return false

##### 5.2.3 Signature.php

The signature class serves as the encapsulation of the signature tuple (r,s). It is a PHP object, containing r,s as private variables with publicly accessible setters and getters. This class is used to store the signature meaningfully while it is being passed between the PublicKey and PrivateKey classes.

#### 5.3 Elliptic Curve Diffie-Hellman Key Agreement

∙ EcDHInterface represents all operations involved in EcDH for dual key encryption along with methods that utilize ECDH as a dual key encryption scheme, namely:

public function __construct(Point g); public function calculateKey(); public function getPublicPoint(); public function setPublicPoint(Point q); public function encrypt(string); public function decrypt(string); public function encryptFile(path); public function decryptFile(path);

##### 5.3.1 EcDH.php

The class has 5 instance variables:

■ for storing the generator point

■ for storing an object instance’s own public Point

■ for storing a public point received from another object instance

■ the private key associated with the current object instance

■ the shared key as a product of successful key agreement using ECDH.

Interaction between Alice and Bob to establish a shared secret is of the form:

g = NISTcurve::generator_192(); Alice = new EcDH(g); Bob = new EcDH(g); //Alice and bob generate their private keys and public Point pubPointA = Alice->getPublicPoint(); pubPointB = Bob->getPublicPoint(); //Alice sends Bob her public key and vice versa Alice->setPublicPoint(pubPointB); Bob->setPublicPoint(pubPointA); //key_A == key_B key_A = Alice->calculateKey(); key_B = Bob->calculateKey();

Description of Algorithms

The constructor serves only to populate the generator point for ECDH.

When called, this method generates a pseudo-random number ”secret” between 0 and the order of the generator point. Upon successful generation it returns the public point secret*Generator.

This method is used to set a public point that was received from the person wishing to establish secure communication through an untrusted channel.

The calculateKey method’s purpose is to finally establish the shared secret. When both parties call this method, they both arrive at the same key. Find the explanation of correctness behind ECDH in Section 3.

public function encrypt(string); public function decrypt(string); public function encryptFile(path); public function decryptFile(path);

The methods above are demonstrations of how a dual-key encryption scheme may be used with the ECDH shared key agreement protocol. The first pair of methods may be used for arbitrary strings. For hashing the x value of the generated shared secret, the implementations use SHA256. This hash is then fed into the 256 bit EAS encryption function in CBC mode. The methods which operate on files are identical to the previous two, but are designed to read in a file as the message to be communicated between Alice and

Bob.

Note: The dual key encryption/decryption algorithm uses AES 256 for two way encryption. This may be substituted by other two way encryption functions as long as the function used to encrypt the message is identical to the one used to decrypt the message.

#### 5.4 Test Suite and Related Source Code

The PHP-OOP includes a Test Suite, along with a class encapsulating NIST published safe curves at various key-lengths.

##### 5.4.1 TestSuite.php

The TestSuite class may be run in verbose or non-verbose mode. It was written to test the algorithms located in the NumberTheory class, to check NIST curve validity checking according to (X9.62) [Brassham(2004)], Point Validity testing accoding to Appendix B.2.2 of [Brassham(2004)], signature validity testing according to Appendix

B.2.4 of [Brassham(2004)], and perform a Diffie-Hellman Key Agreement Protocol test.

##### 5.4.2 NISTCurve.php

The NISTCurve class is an encapsulation of static methods that contains all NIST published elliptic curves that are approved as secure for elliptic curve cryptography.[NIST(2010a)][NIST(2010b)]

### 6 Uses for Elliptic Curve Cryptography

The fact that the discreet logarithm for elliptic curves problem is difficult to solve means that cryptography based on elliptic curves is secure. As in any public key crypto system, the private key should be kept secret or communicated through a secure channel, in order to maintain the security asymmetric key cryptography provides.

The strength of crypto-schemes using elliptic curves are on par with RSA with the advantage that a smaller key may be used to achieve the same level of encryption strength as RSA does. In elliptic curve cryptography, the key size used does not scale linearly with cryptographic strength as in the case of RSA. For example, the EC key size equivalent of 1024 bit RSA encryption is 160 bits, while doubling the key size of RSA to 2048 bits equates to increasing the key size to 224 bits using ECC.[NSA(2009)] This is beneficial in terms of computation, data transmission, and in domains where space is a premium, such as mobile devices, RFID tags, etc.

Elliptic Curve DSA is useful in applications in which other DSA algorithms were used previously, with the added benefit of smaller key sizes. The uses for digital signatures in general are in the areas of authentication and identity establishment, in message integrity verification and non-repudiation. In the area of authentication, digital signatures are used to authenticate the source of the messages that initiate authentication requests.[NSA(2009)] Digital Signatures may be used along with two-way encryption. This is desirable because even though messages are encrypted between two parties, it is possible to alter the encrypted representation of the message.

By augmenting two way encryption with digital signatures, it is possible to verify if the original message was altered. Another important use for digital signatures is non-repudiation of origin, where an entity initially signing a message is unable to later deny having signed the message. ECDSA lends smaller key lengths to the use of DSA with higher level of security compared to RSA if identical length keys are used.

The Diffie-Hellman key agreement protocol is used in everyday applied computer science in TLS (Transport Layer Security) to provide perfect forward secrecy. TLS is a ubiquitous method for perfect forward secrecy, appearing in the HTTPS protocol, as well as other software, such as the OpenSSH project.[OpenBSD(2010)] Also, because PHP is mostly a domain-specific language which focuses on the World Wide Web as its domain, having an application level protocol enables developers to employ ECDH as a means to achieve secure communication via an unsecured channel, without third party validation. The lack of third party validation would make the same assumption that OpenSSH makes, namely that the two parties identity is established at the first time of contact. In the case of secure web services communication, the crypto scheme similar to OpenSSH may be used. The advantage this provides to web service level communication is that the web services may not have to communicate through HTTPS, but are able to achieve encrypted communication among them that is on par or exceeds the current mainstream RSA key lengths used as HTTPS certificates.

### References

[Wade Trappe(2006)]L. C. W. Wade Trappe, Introduction to Cryptography with

Coding Theory, second edition ed., S. Yagan, Ed. Pearson, 2006.

[Zandstra(2008)]M. Zandstra, PHP Objects, Patterns, and Practice, second edition,

Ed. Apress, 2008.

[Washington(2003)]L. Washington, Elliptic Curves: Number Theory and

Cryptography. Chapman & Hall / CRC, 2003.

[Darrel Hankerson(2004)]S. V. Darrel Hankerson, Alfred Menezes, Guide to Elliptic

Curve Cryptography. Springer, 2004.

[I. Blake(1999)]N. S. I. Blake, G. Seroussi, Elliptic Curves in Cryptography.

Cambridge University Press, 1999.

[Brassham(2004)]L. E. Brassham, The Elliptic Curve Digital Signature

Algorithm Validation System (ECDSAVS). NIST, 2004. [Online]. Available:

http://csrc.nist.gov/groups/STM/cavp/documents/dss/ECDSAVS.pdf

[NIST(2010a)]NIST. (2010) Fips 186-2. digital signature standard (dss). [Online].

Available: http://csrc.nist.gov/publications/fips/archive/fips186-2/fips186-2.pdf

[NIST(2010b)]——. (2010) Digital signature standard (dss). [Online]. Available:

http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf

[NSA(2009)]NSA. (2009, January) The case for elliptic curve cryptography. [Online].

Available: http://www.nsa.gov/business/programs/elliptic_curve.shtml

[OpenBSD(2010)]OpenBSD. (2010, 11) Openssh keeping your communities secret.

[Online]. Available: http://www.openssh.com/

### 7 Appendix A: Hardware

The gmp and bcmath tests were run on the follwing hardware:

Processor Name:Intel Core 2 Duo Processor Speed: 2.4 GHz Number Of Processors: 1 Total Number Of Cores: 2 L2 Cache: 4 MB Memory: 4 GB Bus Speed: 800 MHz

### 8 Appendix B: Test Suite Performance using GMP

--------- START NEXT PRIME TEST --------- Next prime took: 0.0036690235137939 seconds. --------- END NEXT PRIME TEST --------- --------- START SQUARE ROOT MOD P TEST --------- Square roots mod 31 took: 0.12426710128784 seconds. --------- END SQUARE ROOT MOD P TEST --------- --------- START MULTIPLICATIVE INVERSE MOD P TEST --------- Multiplicative inverse mod arbitrary primes took: 1.1855871677399 seconds. --------- END MULTIPLICATIVE INVERSE TEST --------- --------- START ELLIPTIC CURVE ARITHMETIC TEST --------- Elementary EC arithmetic took: 0.0085620880126953 seconds. --------- END ELLIPTIC CURVE ARITHMETIC TEST --------- --------- START NIST PUBLISHED CURVES TEST --------- NIST curve validity checking (X9.62) took: 0.2227098941803 seconds. --------- END NIST PUBLISHED CURVES TEST --------- --------- START POINT VALIDITY TEST --------- Point validity testing (ECDSAVS.pdf B.2.2) took: 0.19945812225342 seconds. --------- END POINT VALIDITY TEST --------- --------- START SIGNATURE VALIDITY TEST --------- Signing and verification tests from ECDSAVS.pdf B.2.4 took: 3.7693610191345 seconds. --------- END SIGNATURE VALIDITY TEST --------- --------- START DIFFIE HELLMAN KEY EXCHANGE TEST --------- Diffie Hellman Dual Key Agreement encryption took: 0.31024312973022 seconds. --------- END DIFFIE HELLMAN KEY EXHANGE TEST --------- TEST SUITE TOTAL TIME : 5.8242769241333 seconds.

### 9 Appendix C: Test Suite Performance using bcmath

--------- START NEXT PRIME TEST --------- Next prime took: 0.17068219184875 seconds. --------- END NEXT PRIME TEST --------- --------- START SQUARE ROOT MOD P TEST --------- Square roots mod 31 took: 0.014307022094727 seconds. --------- END SQUARE ROOT MOD P TEST --------- --------- START MULTIPLICATIVE INVERSE MOD P TEST --------- Multiplicative inverse mod arbitrary primes took: 5.2367839813232 seconds. --------- END MULTIPLICATIVE INVERSE TEST --------- --------- START ELLIPTIC CURVE ARITHMETIC TEST --------- Elementary EC arithmetic took: 0.22237086296082 seconds. --------- END ELLIPTIC CURVE ARITHMETIC TEST --------- --------- START NIST PUBLISHED CURVES TEST --------- NIST curve validity checking (X9.62) took: 95.086047887802 seconds. --------- END NIST PUBLISHED CURVES TEST --------- --------- START POINT VALIDITY TEST --------- Point validity testing (ECDSAVS.pdf B.2.2) took: 94.691728115082 seconds. --------- END POINT VALIDITY TEST --------- --------- START SIGNATURE VALIDITY TEST ---------

Signing and verification tests from ECDSAVS.pdf B.2.4 took: 1514.5250930786 seconds. ——— END SIGNATURE VALIDITY TEST ——— ——— START DIFFIE HELLMAN KEY EXCHANGE TEST ——— Diffie Hellman Dual Key Agreement encryption took: 80.673988103867 seconds. ——— END DIFFIE HELLMAN KEY EXHANGE TEST ——— TEST SUITE TOTAL TIME : 1790.6268291473 seconds.

If this source code helps you with a project you are working on, I would appreciate due credit. If you use my source for commercial purposes, please donate

Note: To try this source, please make sure you have the gmp, or bcmath, and the mcrypt extension installed and configured in PHP.

Source Code: https://github.com/mdanter/phpecc.

pdf of this post: [click here to download].