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.