ds.ov2.util
Class Security_parameter

java.lang.Object
  ds.ov2.util.Security_parameter

public class Security_parameter
extends Object

Security estimates for RSA keys and exponent length choice. Based on the estimations of Lenstra in his article "Key length" in the Handbook of Information Security, this class can estimate the security level of an RSA key size in a given year and select a suitable exponent length that achieves the same security level for the descrete logarithm problem.

Static class.

CPP Preprocessing

no cpp preprocessing needed

Execution Environment:

host

Author:

Hendrik Tews

Version:

$Revision: 1.9 $

Last Commit:

$Date: 2010-03-12 15:40:22 $ by $Author: tews $

Nested Class Summary

static class

Security_parameter.Calibration Record containing the necessary data for calibrating the machinery for estimating the security parameters.

Field Summary

private static double	one_third Constant 1/3 with value 0.3333333333333333
static Security_parameter.Calibration	rsa_2004_estimation Calibration data from Lenstra's "Key length" article.
static Security_parameter.Calibration	rsa_768_break_2009 Calibration from the RSA 768 factorization in 2009.
private static double	rsa_alpha An RSA related constant in the estimations of Lenstra.

Constructor Summary

protected

Security_parameter() Static class, object creation disabled.

Method Summary

static int	exponent_length_for_modulus_length_full_byte(int year, int modulus_length, Security_parameter.Calibration cal) Same as exponent_length_for_modulus_length but round the exponent length up to the next multiple of 8.
static int	exponent_length_for_modulus_length(int year, int modulus_length, Security_parameter.Calibration cal) Compute an exponent length for an RSA key length suitable up to year year.
(package private) static double	L(int log_2_n, double r, double alpha) The L function to describe the subexponential complexity of number factoring.
static double	rsa_cost(int year, int modulus_length, Security_parameter.Calibration cal) Cost in dollar days that is needed to break an RSA key of size modulus_length in the year year.
static double	rsa_level(int year, int modulus_length, Security_parameter.Calibration cal) Security level an RSA key length provides in a given year.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

rsa_2004_estimation

public static Security_parameter.Calibration rsa_2004_estimation

Calibration data from Lenstra's "Key length" article. In 2004 it was estimated that breaking an 1024 bit RSA modulus would cost 400 million dollar days.

From this data the security level is estimated as follows. In 1982 40 Million dollar days correspond to security level 56 (DES). With Moores law the same effort corresponds to security level 70.6 in 2004. Therefore an 1024 bit key had security level 74 in 2004.

rsa_768_break_2009

public static Security_parameter.Calibration rsa_768_break_2009

Calibration from the RSA 768 factorization in 2009. In 2009 the RSA 768 challenge was broken, see "Factorization of a 768-bit RSA modulus" by Thorsten Kleinjung et. al. The authors estimated that 2000 years of computing on a single AMD Opteron 2.2 GHz core were needed for the factorization. In early 2010 an rack with an 2-core Opteron was offered at 700 dollars. This would make 255 Million dollar days. Bying en-mass probably gives a reduction, so I take 100 Million dollar days.

The key was broken in 2009 with quite some effort, so I assume that 768 bit keys were secure until 2008, ie, the key had security level 73 in 2008. Because of the double Moores-law effect the factorization would have cost about 200 Million dollar days in 2008.

one_third

private static final double one_third

Constant 1/3 with value 0.3333333333333333

See Also:

Constant Field Values

rsa_alpha

private static final double rsa_alpha

An RSA related constant in the estimations of Lenstra. See page 24 of his "Key Length" paper. Has value 1.976.

See Also:

Constant Field Values

Constructor Detail

Security_parameter

protected Security_parameter()

Static class, object creation disabled.

Method Detail

L

static double L(int log_2_n,
                double r,
                double alpha)

The L function to describe the subexponential complexity of number factoring. See page 21 of Lenstras "Key Length" paper. In Lenstras version the first argument of the L function is the key itself. Here we take the key length as first argument (which is the logarithm to the base 2 of the key).

Parameters:

log_2_n - key length

r - distribution between polynomial and exponential parts, r = 0 gives polynomial complexity, r = 1 exponential complexity.

alpha - some factor

Returns:

the value of the L function, which is proporional to the effort needed to factor an RSA key of log_2_n bits.

rsa_cost

public static double rsa_cost(int year,
                              int modulus_length,
                              Security_parameter.Calibration cal)

Cost in dollar days that is needed to break an RSA key of size modulus_length in the year year. The estimation is based on a calibraion record and the following:

• by Moores low every 18 month the hardware is twice as fast and therefore the cost drops to 50% every 18 month
• advances in number factoring half the needed effort every 18 month
• Moores low and the advances in number factoring are independent, so that effectively the cost drops to 50% every 9 month.

Parameters:

year - year for which the cost should be estimated

modulus_length - the bit length of the RSA modulus

cal - Calibration data, if null rsa_2004_estimation is used

Returns:

estimated costs in dollar days

rsa_level

public static double rsa_level(int year,
                               int modulus_length,
                               Security_parameter.Calibration cal)

Security level an RSA key length provides in a given year. The estimation is based on a calibraion record and the following:

• advances in number factoring half the effort needed every 18 month

The security level of a given RSA key length decreases with time because of the estimated advances in number crunching.

Parameters:

year - year for which the security level should be estimated

modulus_length - the bit length of the RSA modulus

cal - Calibration data, if null rsa_2004_estimation is used

Returns:

estimated security level

exponent_length_for_modulus_length

public static int exponent_length_for_modulus_length(int year,
                                                     int modulus_length,
                                                     Security_parameter.Calibration cal)

Compute an exponent length for an RSA key length suitable up to year year. Based on the estimated security level (compare rsa_level) an exponent length is chosen that provides the same security. For the exponent length we assume that an exponent of length 2n privides n bits of security against solving the discrete logarithm problem.

For a fixed RSA key length the returned exponent length decreases with time because of the assumed advances in number crunching.

The estimations of Lenstra on which the computations are bases are certainly only valid for a relatively narrow range of the arguments. For key length below 512 bits the results are probably only good for amusement. Nevertheless this is the main method to choose exponent length' for key sizes from 32-2048 bits. Simply because there is no sensible way to choose an exponent length.

For very small RSA key sizes the estimated security level becomes negative (not sure what that means). As minimal exponent length 2 is returned in such cases.

Parameters:

year - year for which the cost should be estimated

modulus_length - the bit length of the RSA modulus

cal - Calibration data, if null rsa_2004_estimation is used

Returns:

exponent length providing the same security

exponent_length_for_modulus_length_full_byte

public static int exponent_length_for_modulus_length_full_byte(int year,
                                                               int modulus_length,
                                                               Security_parameter.Calibration cal)

Same as exponent_length_for_modulus_length but round the exponent length up to the next multiple of 8.

Parameters:

year - year for which the cost should be estimated

modulus_length - the bit length of the RSA modulus

cal - Calibration data, if null rsa_2004_estimation is used

Returns:

exponent length providing the same security rounded up to the next byte boundary