Source:
www.rsasecurity.com/rsalabs
How is the RSA
algorithm used for authentication
and digital
signatures?
The RSA
public-key cryptosystem can be used to authenticate or identify
another person
or entity.
The reason it
works well is because each entity has an associated private key
which
(theoretically) no one else has access to.
This allows for
positive and unique identification.
Suppose Alice
wishes to send a signed message to Bob. She applies a hash
function to the
message to create a message digest which serves as a
"digital
fingerprint" of the message.
She then
encrypts the message digest with her private key, creating the digital
signature she
sends to Bob along with the message itself.
Bob, upon
receiving the message and signature, decrypts the signature
with Alice's
public key to recover the message digest. He then hashes the message
with the same
hash function Alice used and compares the result to the message digest
decrypted from
the signature. If they are exactly equal, the signature has
been
successfully verified and he can be confident the message did indeed
come from Alice.
If they are not equal, then the message either originated
elsewhere or was
altered after it was signed, and he rejects the message.
Anybody who
reads the message can verify the signature. This does not
satisfy
situations where Alice wishes to retain the secrecy of the
document. In
this case she may wish to sign the document, then encrypt it
using Bob's
public key. Bob will then need to decrypt using his private
key and verify
the signature on the recovered message using Alice's public
key.
Alternately, if it is necessary for intermediary third parties to
validate the
integrity of the message without being able to decrypt its
content, a
message digest may be computed on the encrypted message, rather
than on its
plaintext form.
In practice, the
public exponent in the RSA algorithm is usually much
smaller than the
private exponent. This means that verification of a
signature is
faster than signing. This is desirable because a message will
be signed by an
individual only once, but the signature may be verified
many times.
It must be
infeasible for anyone to either find a message that hashes to a
given value or
to find two messages that hash to the same value. If either
were feasible,
an intruder could attach a false message onto Alice's
signature.
Some Hash
functions such as MD5 and SHA have been designed specifically
to have the
property that finding a match is infeasible, and are therefore considered
suitable for use
in cryptography.
One or more
certificates may accompany a digital
signature. A
certificate is a signed document that binds the public key to
the identity of
a party. Its purpose is to prevent someone from
impersonating
someone else. If a certificate is present, the recipient (or
a third party)
can check that the public key belongs to a named party,
assuming the
certifier's public key is itself trusted.
Elliptic curve
cryptosystems: Public-key cryptosystem
Elliptic curve
cryptosystems were first proposed independently by Victor
Miller and Neal
Koblitz in the mid-1980s.
At a high level,
they are analogs of existing public-key cryptosystems in which
modular
arithmetic is replaced by operations defined over elliptic curves.
The elliptic
curve cryptosystems that have appeared in
the literature
can be classified into two categories according to whether
they are analogs
to the RSA system or to discrete logarithm based systems.
Just as in all
public-key cryptosystems, the security of elliptic curve
cryptosystems
relies on the underlying hard mathematical problems.
It turns out
that elliptic curve analogs of the RSA system
are mainly of
academic interest and offer no practical advantage over the
RSA system,
since their security is based on the same underlying problem,
namely integer
factorization. The situation is quite different with
elliptic curve
variants of discrete logarithm based systems.
The security of
such systems depends on the following hard problem:
Given two points G and Y on an elliptic curve such that Y = kG
(that is, Y is G added to itself k times), find the integer k.
This problem is
commonly referred to as the elliptic curve discrete logarithm
problem.
Presently, the
methods for computing general elliptic curve discrete
logarithms are
much less efficient than those for factoring or computing
conventional
discrete logarithms. As a result, shorter key sizes can be
used to achieve
the same security of conventional public-key
cryptosystems,
which might lead to better memory requirements and improved
performance. One
can easily construct elliptic curve encryption,
signature, and
key agreement schemes by making analogs of discrete logarithm
based system
such as Diffie-Hellman scheme.
These variants
appear to offer certain implementation advantages over the original
schemes, and
they have recently drawn more and more attention from both the
academic
community and the industry.
The main
attraction of elliptic curve cryptosystems over other public-key
cryptosystems is
the fact that they are based on a different, hard
problem. This
may lead to smaller key sizes and better performance in
certain public
key operations for the same level of security.
Very roughly
speaking, elliptic curve cryptosystems with a 160-bit key offer
the same
security of the RSA system and discrete logarithm based systems with
a 1024-bit key,
roughly 6-times.
As a result, the
length of the public key and private key is much shorter
in elliptic
curve cryptosystems.
In terms of
speed, however, it is quite difficult to give a
quantitative
comparison, partly because of the various optimization
techniques one
can apply to different systems. It is perhaps fair to say
the following:
Elliptic curve cryptosystems are faster than the
corresponding
discrete logarithm based systems. Elliptic curve
cryptosystems
are faster than the RSA system in signing and decryption,
but slower in
signature verification and encryption.
With academic
advances in attacking different hard mathematical problems
both the
security estimates for various key sizes in different systems and
the performance
comparisons between systems are likely to change.
DES : Symmetric (Secret-key)
cryptosystem
DES, an acronym
for the Data Encryption Standard, is the name of the
Federal
Information Processing Standard (FIPS) 46-3, which describes the
data encryption
algorithm (DEA).
DEA is an
improvement of the algorithm Lucifer developed by IBM in the
early 1970s.
While the algorithm was essentially designed by IBM, the NSA
and NBS played a
substantial role in the final stages of the development.
The DEA, often
called DES, has been extensively studied since its publication
and is the best
known and widely used symmetric algorithm in the world.
The DEA has a
64-bit block size and uses a 56-bit key
during execution
(8 parity bits are stripped off from the full 64-bit
key). The DEA is
a symmetric cryptosystem, specifically a 16-round Feistel
cipher and was
originally designed for implementation in hardware.
When used for
communication, both sender and receiver must
know the same
secret key, which can be used to encrypt and decrypt the
message, or to
generate and verify a message authentication code (MAC).
The DEA can also
be used for single-user encryption, such as to store
files on a hard disk
in encrypted form. In a multi-user environment,
secure key
distribution may be difficult; public-key cryptography provides
an ideal
solution to this problem.
NIST has
re-certified DES (FIPS 46-1, 46-2, 46-3) every five years.
FIPS 46-3
reaffirms DES usage as of October 1999, but
single DES is
permitted only for legacy systems. FIPS 46-3 includes a
definition of
triple-DES (TDEA)
On 5/26/2002,
the Advanced Encryption Standard was officially approved to become
the successor to
DES by FIPS (Federal Information Processing Standard) 197.
AES
The AES is the
Advanced Encryption Standard. The AES was issued as FIPS
PUB 197 by NIST
standard is the successor to DES.
In January 1997, the
AES initiative was announced and in September 1997 the public
was invited to
propose suitable block ciphers as candidates for the AES.
The AES
algorithm was selected in October 2001 and the standard was published in
November
2002.
NIST's intent
was to have a cipher that will remain secure well into the next century.
AES supports key
sizes of 128 bits, 192 bits, and 256 bits, in contrast to
the 56-bit keys
offered by DES.
The AES
algorithm resulted from a multi-year evaluation process led by
NIST with
submissions and review by an international community of
cryptography
experts. The Rijndael algorithm, invented by Joan Daemen and
Vincent Rijmen,
was selected as the standard.
Over time, many
implementations are expected to upgrade to AES, both
because it
offers a 128-bit key size, and because it is a federal
standard.
Government Agencies: NIST and
NSA
1.
NIST
NIST is an
acronym for the National Institute of Standards and Technology,
a division of
the U.S. Department of Commerce. NIST was formerly known as
the National
Bureau of Standards (NBS). Through its Computer Systems
Laboratory it
aims to promote open systems and interoperability that will
spur the
development of computer-based economic activity. NIST issues
standards and
guidelines intended to be adopted in all computer systems in
the U.S., and
also sponsors workshops and seminars. Official standards are
published as
FIPS (Federal Information Processing Standards) publications.
In 1987 Congress
passed the Computer Security Act, which authorized NIST
to develop
standards for ensuring the security of sensitive but
unclassified
information in government computer systems. It encouraged
NIST to work
with other government agencies and private industry in
evaluating
proposed computer security standards.
NIST issues
standards for cryptographic algorithms that U.S. government
agencies are
required to use. A large percentage of the private sector
often adopts
them as well.
In January 1977,
NIST declared DES as the official U.S. encryption standard and
published it as
FIPS 46.
DES soon became
a de facto standard throughout the United States.
Several years
ago, NIST was asked to choose a set of cryptographic
standards for
the U.S., this has become known as the Capstone project.
After a few
years of rather secretive deliberations,
NIST, in
cooperation with the NSA, issued proposals for various standards
in cryptography.
The combination of these proposals,
including
digital signatures (DSS) and data encryption (the Clipper chip),
formed the
Capstone project.
NIST has been
criticized for allowing the NSA too much power in setting
cryptographic
standards, since the interests of the NSA sometimes conflict
with that of the
Commerce Department and NIST.
Yet, the NSA has
much more experience with cryptography, and many more
qualified
cryptographers and cryptanalysts than does NIST so it is perhaps
unrealistic to
expect NIST to forego such readily available assistance.
For more
information on NIST, visit their web site at
http://www.nist.gov/.
2. NSA
NSA is the
National Security Agency, a highly secretive agency of the U.S.
government
created by Harry S. Truman in 1952. The NSA's very existence
was kept secret
for many years.
The NSA has a
mandate to listen to and decode all foreign
communications
of interest to the security of the United States. It has
also used its
power in various ways to slow the spread of publicly
available
cryptography in order to prevent national enemies from employing
encryption
methods that are presumably too strong for the NSA to break.
As the premier
cryptographic government agency, the NSA has huge financial
and computer resources and employs
a host of cryptographers. Developments
in cryptography
achieved at the NSA are not made public; this secrecy has
led to many
rumors about the NSA's ability to break popular cryptosystems
like DES, as
well as rumors that the NSA has secretly placed weaknesses,
called
``trapdoors,'' in government-endorsed cryptosystems.
These rumors
have never been proved or disproved. Also the
criteria used by
the NSA in selecting cryptography standards have never
been made
public.
Recent advances
in the computer and telecommunications industries have
placed NSA
actions under unprecedented scrutiny, and the agency has become
the target of
heavy criticism for hindering U.S. industries that wish to
use or sell
strong cryptographic tools. The two main reasons for this
increased
criticism are the collapse of the Soviet Union and the
development and
spread of commercially available public-key cryptographic
tools. Under
pressure, the NSA may be forced to change its policies.
The NSA's
charter limits its activities to foreign intelligence. However,
the NSA is
concerned with the development of commercial cryptography,
since the
availability of strong encryption tools through commercial
channels could
impede the NSA's mission of decoding international
communications.
In other words, the NSA is worried that strong commercial
cryptography may
fall into the wrong hands.
The NSA has
stated that it has no objection to the use of secure
cryptography by
U.S. industry. It also has no objection to cryptographic
tools used for
authentication, as opposed to privacy. However, the NSA is
widely viewed to
be following policies that have the practical effect of
limiting and/or
weakening the cryptographic tools used by law-abiding U.S.
citizens and
corporations.
The NSA exerts
influence over commercial cryptography in several ways. NSA
serves as an
advisor to the Bureau of Export Administration (BXA) at the
Commerce
Department, which is the front-line agency on export
determination.
In the past, BXA generally has not approved export of
products used
for encryption unless the key size is strictly limited. It
did, however,
approve export of any products used for authentication
purposes only,
no matter how large the key size, as long as the product
cannot be easily
converted to be used for encryption. Today the situation
is different
with dramatically relaxed restrictions on export regulations.
The NSA has also
blocked encryption methods from being published or
patented, citing
a national security threat.
Additionally,
the NSA serves an ``advisory'' role to NIST in the
evaluation and
selection of official U.S. government computer security
standards. In
this capacity, it has played a prominent and controversial
role in the
selection of DES and in the development of the group of
standards known
as the Capstone project. The NSA can also exert market
pressure on U.S.
companies to produce (or refrain from producing)
cryptographic
goods, since the NSA itself is often a large customer of
these companies.
Examples of NSA-supported goods include Fortezza,
the Defense
Messaging System (DMS), and MISSI, the Multilevel Information
System Security
Initiative.
Cryptography is
in the public eye as never before and has become the
subject of
national public debate. The status of cryptography, and the
NSA's role in
it, will probably continue to change over the next few
years.
United States
Cryptography Export/Import Laws
For many years,
the U.S. government did not approve export of
cryptographic
products unless the key size was strictly limited. For this
reason,
cryptographic products were divided into two classes: products
with "strong"
cryptography and products with "weak" (that is, exportable)
cryptography.
Weak cryptography generally means a key size of at most 56
bits in
symmetric algorithms, an RSA modulus of size at most 512 bits, and
an elliptic
curve key size of at most 112 bits.
It should be
noted that 56-bit DES and RC5 keys have been cracked, as well as
a 512-bit RSA
key.
In January 2000,
the restrictions on export regulations were dramatically
relaxed. Today,
any cryptographic product is exportable under a license
exception (that
is, without a license) unless the end-users are foreign
governments or
embargoed destinations (Cuba, Iran, Iraq, Libya, North
Korea, Serbia,
Sudan, Syria, and Taliban-controlled areas of Afghanistan).
Export to
government end-users may also be approved, but under a license.
Why is cryptography
export-controlled?
Strong
cryptography can be used for criminal purposes or even as a weapon
of war. During
wartime, the ability to intercept and decipher enemy communications
is crucial. For
that reason, cryptographic technologies are subject to export controls.
U.S. government
agencies consider strong encryption to be systems that use RSA
with key sizes
over 512 bits or symmetric algorithms (such as triple-DES, IDEA,
or RC5) with key
sizes over 56 bits.
Since government
encryption policy is heavily influenced by the agencies responsible
for gathering
domestic and international intelligence (the FBI and NSA, respectively),
the government
is compelled to balance the conflicting requirements of
making strong
cryptography available for commercial purposes while still
making it
possible for these agencies to break the codes, if need be.
As already
mentioned, the major restrictions on export regulations were eliminated
in the beginning
of the year 2000.
To most
cryptographers, the above level of cryptography - 512 for RSA and
56 for symmetric
algorithms - is not considered ``strong'' at all.
In fact, it is
worth noting that RSA Laboratories has considered this level
of cryptography
to be commercially inadequate for several years.
Government
agencies often prefer to use the terms ``strategic'' and
``standard'' to
differentiate encryption systems. ``Standard'' refers to
algorithms that
have been drafted and selected as a federal standard; DES
is the primary
example. The government defines ``strategic'' as any
algorithm that
requires ``excessive work factors'' to successfully attack.
Unfortunately,
the government rarely publishes criteria for what it
defines as
``acceptable'' or ``excessive'' work factors.