McAfee SECURE sites help keep you safe from identity theft, credit card fraud, spyware, spam, viruses and online scams

Cookie Information

Privacy Information

UK Essays Services:

Free Help:

Radio Frequency Identification - History

Radio Frequency Identification (RFID) is one of the new emerging technologies. It describes a system that transmits the identity of an object or person wirelessly, using radio wave propagation.

This is a flexible technology that is convenient and easy to use. RFID can be a read-only or read/write. RFID technology does not require any contact or line of sight for its operations. It can function under a variety of environmental conditions, and provides a high level of data integrity. And it is well-suited for automatic operation.

RFID History:

The advent of radio technology was the primary prerequisite of Radio Frequency Identification. Guglielmo Marconi first transmitted radio signals across the Atlantic in 1901, since then radio waves have been an important way to send messages—from Morse code to the first voice broadcast in 1906. So, scientists discovered that they could use radio waves for more than just message transmission. (Ref. 11)

Actually, the roots of RFID technology can be traced back to World War II. In 1935, a Scottish physicist Sir Robert Alexander Watson-Watt invented radar which was used by the Germans, Japanese, Americans and British. The function of radar is to warn of approaching planes while they are still miles away. But, the problem was that there was no way to identify which planes belonged to the enemy and which were a country's own pilots returning from a mission.

For solving this problem, a system was developed. A transponder was placed on Allied aircraft so that by giving the appropriate response to an interrogating signal, a "friendly" aircraft could automatically be distinguished from a "foe".   This system was known as the IFF System (Identify: Friend or Foe). Even present day commercial and private aviation traffic control is still based on this system.  In IFF system, a transmitter was put on each plane (Allied plane). It started broadcasting a signal back that identified the aircraft as friendly when it received signals from radar stations on the ground. As RFID works on this same basic concept obviously it was the first use of RFID. .

Advances in radar and RF communications systems continued through the 1950s and 1960s. In the United States, Europe and Japan, scientists and academics did research and presented papers explaining how RF energy could be used to identify objects remotely.

In the late 60's or early 70's, the need for security and safety surrounding the use of nuclear materials drove further development of RFID "tagging" of equipment and personnel.  Earlier, RFID development was stuck with only government labs mainly defense which was later in 1977 transferred to the public sector by Los Alamos Scientific Laboratories (LASL) resulting in two companies forming to explore possible civilian uses.  These companies were Amtech (presently part of Transcore) in New Mexico and Identronix Research in Santa Cruz, California.

On January 23, 1973, Mario W. Cardullo first claims to have received the U.S. patent for an active RFID tag with rewritable memory. Charles Walton, a California entrepreneur, also received a patent for a passive transponder on that same year. He used RFID to unlock a door without a key. A card with an embedded transponder communicated a signal to a reader near the door. When the reader detected a valid identity number stored within the RFID tag, the reader unlocked the door. Later Walton licensed the technology to Schlage, a lock maker, and other companies

While most of the early Identronix and Amtech research was based on 900 MHz and 900/1800 MHz systems, later there were RFID products at LF, MF, VHF, UHF, and microwave frequencies.  By 1984, RFID tags were regularly being manufactured by several U.S. and European companies.

The 90's were a significant decade for RFID. During this decade, the wide scale deployment of electronic toll collection in the United States had done using RFID technology. Between 1999 and 2003, the Auto-ID Center gained the support of more than 100 large end-user companies, plus the U.S. Department of Defense and many key RFID vendors. It opened many research labs in Australia, the United Kingdom, Switzerland, Japan and China.

With the growing interest of RFID into the item management work and the opportunity for RFID to work along side bar code, it becomes difficult in the later part of this decade to count the number of companies who enter the marketplace. Many have come and gone, many are still here, many have merged, and there are many new players

Table 1: Decades of RFID Technology

Some US Patents of interest (Note: a search of the US Patent Office alone will reveal over 350 patents related to RFID and its use).

Table 2: RFID Patents in US

An RFID system is mainly composed of two components:-

Figure 1: shows a RFID system setup.

An RFID tag is an information carrying chip. It generally carries the identity of the associated object, but can also store other information relating to the object. Normally, RFID tags are tiny microchips with memory and an antenna coil, thinner than paper and some only 0.3mm across.

Figure 2: A regular RFID tag

The RFID tags can be classified my two methods, one by their operating frequencies and the other by determining how they acquire their operating power.

The RFID tags can be classified by their operating frequencies. Tags operating

below 135 kHz are referred to as Low Frequency (LF) tags, those operating at 13.56 MHz are as High Frequency (HF) tags, those operating at 868 MHz and 915 MHz are Ultra High Frequency (UHF) tags, and those at 2.43 GHZ is Microwave tags.

Table 3: RFID usage Frequencies

Another very common way of classifying tags is by how they acquire their operational

Power and according to this RFID tags are classified to:-

Passive RFID tags can be as small as 0.3mm and don't require batteries. Rather, they are powered by the radio signal of a RFID reader, which "wakes them up" to request a reply. Passive RFID tags can be read from a distance of up to 20 feet. The major drawback of this type of tags is their limited reading distance due to the limited range and strength of the electric and magnetic fields.

Active tags are battery powered devices that have an active transmitter onboard. Unlike passive tags, active tags generate RF energy and apply it to the antenna. This autonomy from the reader means that they can communicate at distances of over several kilometers. Active RFID tags may be read-write, meaning data they contain can be written over.

Semi-passive tags are tags that incorporate a battery for internal processing, but utilize the energy from the reader to transmit the reply [6]. These tags combine the advantages and disadvantages of both passive and active tags. As they incorporate a battery, they can not be made as small as passive tags, but they have longer reading distances as they only need energy from the reader to send the reply, not for the internal processing. Their lifetimes will also generally be longer than for active tags.

Figure 3: Different shapes and forms RFID tag

An RFID reader retrieves information stored on a tag by broadcasting a signal through its antenna. This transmission prompts the tag to respond with its own transmission. RFID readers play the same basic role as bar code scanners. But a bar code scanner generally captures information one bar code at a time. On the other hand, a RF reader is capable of reading multiple tags within its transmission field. There are two types of RFID readers:

As the name suggests, these devices can only query or read information from a nearby RFID tag. These readers are found in fixed, stationery applications as well as portable, handheld varieties.

Also known as encoders, these devices read and also write (change) information in an RFID tag. Such RFID encoders can be used to program information into a "blank" RFID tag. A common application is to combine such a RFID reader with a Barcode printer to print "smart labels". Smart labels contain a UPC Barcode on the front with an RFID tag embedded on the back.

Figure 4: Various RFID readers

Other than tag and reader to complete the RFID technology, we also need a Data accumulator and software.

This is any device, such as a laptop computer, an electronic scale head or a hand-held computer, that is capable of communicating with a transceiver and accepting the information from it.

The software is considered by many to be the heart and soul of a comprehensive RFID system. The transference of data between transponder and transceiver, and between transceiver and data accumulation, takes place electronically But, it is the software that allows us to actually tie electronic identity to production and management information, massage the data and share the information with others.

Radio Frequency Identification is a way for computers to communicate with any object. An RFID “tag”, which is attached to an object, broadcasts its identification information which is received by a reading device that is within proximity of the tag. The information the reader obtains from the tag, typically an identification number, is then stored by a computer system.

Figure 5: radio system

When an RFID tag passes through the field of the scanning antenna, it detects the activation signal from the antenna. That "wakes up" the RFID chip, and it transmits the information on its microchip to be picked up by the scanning antenna. Software programs and databases keep track of when and where the specific tags have been read. So that when a tag is read, the stored data is showed in the display screen of the computar.

RFID

Reader

RS 232 cable

RFID tag

Requesting data

data

Transmitting data

Display unit

Figure 6: how the technology works

Even though RFID technology has many expected benefits, it also raises major issues in the areas of privacy, security, technological reliability, and international compatibility.

‘One key challenge for decision-makers is to create a common vision and a set of goals on how RFID can keep the world more innovative and competitive in the world economy. At the same time citizens must have the tools and freedom of choice they need to protect their privacy and security'. (Ref .9)

Current trends indicate that the RFID market will grow fast in the next 10 years. With 1.02 billion tags sold in 2006, the value of the market, including hardware, systems and services, is expected to increase by a factor of six between 2007 and 2017. Business applications using RFID such as transport and logistics, access control, real time location, supply chain management, manufacturing and processing, agriculture, medicine and pharmaceuticals, are expected to grow strongly. But RFID devices will also influence Government (e.g. eGovernment, national defense and security), and consumer sectors (e.g. personal safety, sports and leisure, smart homes and smart cities). (Ref. 9)

Wal-Mart, the world's second largest company, is deploying RFID technology in its stores. The Department of Defense (DOD) is as well embracing this technology. The DOD purchases not only just multi-million dollar military equipment, but more than $20 billion dollars in consumer products and is seeking to make the supply chain more efficient. Companies like Microsoft, IBM, and Philips Electronics, which recently made product enhancement announcements in this area. (Ref. 14)

Presently, RFID is mainly using in the following fields: (Ref. 42)

One of the most widely used applications of RFID is EAS or Electronic Article Surveillance systems. Two commercial companies named Sensormatic and Checkpoint did lots of development in EAS system using RFID. Both the companies were established in the late ‘60s. To limit shoplifting by the use of RFID tags is behind EAS systems

Currently contact-based smartcards are used in a variety of applications involving access control, ticketing, payment systems etc. It relies on electrical contacts linking the reader and an integrated circuit on the card. In the contact less smartcards based on RFID, no physical contact is necessary. As a result contact less smartcards can be used in more harsh environments than regular contact-based smartcards. Also, it gives relive the user of the physical effort of inserting the card into the reader. This type of card can be read while it is still in the user's handbag

In the traditional transport system, speed limits, stop signs and control information have been relayed to the driver by the use of signs and light signals. However, the RFID can be utilized to convey the same information. Attached to the underside of each locomotive is an RFID reader. In RFID tags located on the sleepers, restrictions etc. along the track can then be encoded. When the locomotive travels past a sleeper with a tag, the tag is read and the information is displayed to the driver. An autopilot function may also be realized in the same way.

While filling gas bottles, it is very important that the gas is filled on the correct type of bottle. A mismatch between the gas and bottle may be fatal. However, each gas bottle and filling station is tagged with an RFID tag and equipped with a reader respectively; then mismatches can be easily identified.

Also, it can be used to distribute the costs of waste disposal fairly. The entire responsible for waste disposal can keep track of the amount of waste generated by each participant by tagging each waste disposal bin, and equipping each garbage truck with a reader and some way of measuring the amount of waste. This thing helps us to calculate a fair distribution of the costs.

It is another important use of RFID. For example, we can improve the assembly line production method. We can tag each object moving down with a tag containing relevant data to the production process. The data in the tag is instantly available at each new station along the line.

Presently, at most of the border, A new picture is taken to compare to the one stored in the passport. After that, if the two images match then only the passport holder is allowed to pass. This helps us to increase the security of the passport system as automatic facial recognition which is actually much more accurate than manual facial recognition. However, there must be some ways of transferring the picture stored in the passport to the border control so that the comparison can be performed. This can be done using RFID, and passports utilizing this technology are often known as e-passports.

Currently, many European countries and the U.S.A. have decided to include biometric data in their passports, and use RFID to communicate with the chip in the passport.

RFID and bar codes will coexist for many years, although the former technology is likely to gradually replace the latter in some sectors. The widespread item-level tagging of products, though not imminent, is likely to progress as costs go down, standards for RFID frequency and power are defined, end-user knowledge about how the technology works improves and technical hitches are overcome.

Figure 7: Global revenue from RFID related sales grew steadily during past years and expected to continue

The market for RFID interrogators or tag readers is expected to reach $1.14 billion in 2008 for EPC interrogators and $750 million in the same year for other interrogators, such as those for Near Field Communication.

Forecasts by territorial region show that by 2010, 48 percent of RFID tags by volume will be sold in East Asia, followed by 32 percent to North America.

East Asia involves the much higher priced cards rather than labels means that what some of these countries lose in numbers versus the US is compensated to some extent by higher unit price of the tags sold there at present. However, that will change as RFID labels are used in very large numbers in East Asia partly to comply with American and European mandates that consumer goods supplied to them from Asia - their main source of consumer goods - be tagged at pallet, case and, increasingly, item level. Consequently, although China, for the first time, dominates the total RFID business - virtually without exporting - the USA dominates everything beyond the card part. The market will rise to $26.88 Billion in 2017. This includes many new markets that are being created, such as the market for Real Time Locating Systems using active RFID, which will itself be more than $6 Billion in 2017.

Figure 8: Top ten countries using RFID technology by IDTechEx RFID Knowledgebase Q1 2007

There are still a vast number of problems that should be solved before their massive deployment of RFID systems which have emerged as one of the most pervasive computing technologies in history,

One of the main issues is privacy. Products labeled with tags reveal sensitive information when queried by readers, and they do it indiscriminately. A problem closely related to privacy is tracking, or violations of location privacy. This is possible because the answers provided by tags are normally pre-detectable. In fact, most of the times, tags provide always the same identifier, which will allow a third party to easily establish an association between a given tag and its holder or owner. Even in the case in which tags try not to reveal any kind of valuable information that could be used to identify themselves or their holder, there are many situations where, by using an assembly of tags, this tracking will still be possible. Figure below shows the basic types of attacks.

Figure 9: RFID threats

Threats are potential events that cause a system to respond in an unexpected or damaging way. For determining strategies for mitigating the threats, it is useful to categorize them. There are mainly six kinds of threats to RFID. They are listed below: - (Ref. 6)

Spoofing occurs when an attacker successfully poses as an authorized user of a system. Listed below are spoofing threats:-

• A competitor or thief performs an unauthorized inventory of a store by scanning RFID

EPC (Electronic Product Code) tags with an unauthorized reader to determine the types and quantities of items. An unauthorized reader can query the tag for the EPC number because most tags used in the supply chain respond to any reader. The EPC number is only a number. However, because of the standard way of creating an EPC number, an attacker can determine the manufacturer and possibly the product number. It is likely that the number assigned to all manufacturers will become public knowledge as well as the product number after some short period of time.

• An attacker determines what organization is assigned an EPC number by posing as an authorized EPC's global Information Services (IS) Object Name Service (ONS) user. An attacker can pose as an authorized ONS user and submit queries of either gathered EPC numbers or random EPC numbers to ONS. Middleware queries ONS with the EPC number to determine the URL of the database that contains information on this particular EPC number. If an attacker can pose as one of the authorized middleware users, she/he can submit queries and gather URLs determining the location and possible identification of the organization that contains information on the EPC number.

• An attacker determines the complete information about an object by posing as an authorized user of the database referenced by ONS. An attacker can pose as an authorized ONS user and submit queries to ONS gathering URLs and then look up the EPC number in the appropriate database after being authenticated. A user of ONS authenticates itself with the database after finding the location of the database with ONS to find the mapping between the EPC number and information about the product that has the tag. An attacker that poses as an authorized user can determine the manufacturer, product description, and serial number of a case or a large number of cases.

• An attacker poses as an ONS server. It can gather EPC numbers quietly or respond with invalid URLs leading to either a tampering of data or a denial-of-service attack.

Data tampering occurs when an attacker modifies, adds, deletes, or reorders data. Listed below are data tampering threats:-

a. In most cases, an attacker modifies a tag because of the following reasons:-

b. An attacker adds a tag to an object for the following reasons:-

Repudiation threats means when a user denies an action and no proof exists to prove that the action was performed.

• A retailer denies receiving a certain pallet, case, or item. A non-repudiation protocol is required to ensure that neither the sender nor the receiver can deny actions.

• The owner of the EPC number denies having information about the item to which the tag is attached. This could lead to a user being denied warranty repair or returns.

Information disclosure occurs when information is exposed to an unauthorized user. It is a threat to privacy if it is information about an individual.

• A bomb in a restaurant explodes when there are five or more people of same country or organization with RFID enabled products (e.g. e-passports) detected.

• A smart bomb positioned at a street corner explodes when a particular individual with an RFID-enabled passport is detected.

• A smart bomb positioned at a street corner explodes when an individual carrying one or more specific items with tags is detected. An individual could be marked by reading the tags that they typically carry. Or any individual buying certain products could be marked.

• A mugger marks a potential victim by querying the tags in possession of an individual to determine if they are carrying valuable or wanted items.

• An attacker blackmails an individual for having certain merchandise in their possession.

• A fixed reader at a retail counter identifies the tags of a person and shows the similar products on the nearby screen to a person to provide individualized marketing.

• A competitor or thief performs an unauthorized inventory of a store by scanning tags with a reader to determine the types and quantities of items.

• A thief creates a duplicate tag with the same EPC number and returns a forged item for an unauthorized refund.

• A sufficiently powerful directed reader reads tags in your house or car.

Denial-of-service denies service to valid users. This type of threat attacks are easy to accomplish and difficult to guard against.

• An attacker kills tags in the supply chain, warehouse, or store disrupting business operations and causing a loss of revenue.

• A shoplifter carries a blocker tag that disrupts reader communication to conceal the stolen item. An attacker can simulate many RFID tags simultaneously causing the anti-collision to perform singulation (the process in the deterministic anti-collision protocol of systematically choosing one tag to respond) on a large number of tags making the system unavailable to authorized use.The blocker tag, a cheap passive RFID device that simulates many ordinary RFID tags simultaneously and renders specific zones to be private or public, could simulate all RFID tags or it could simulate portions of the EPC address space.

• An attacker carries a special absorbent tag that is tuned to the same frequencies used by the tags. Instead of switching the impedance in and out of the antenna to modulate the reader signal it would just absorb the energy reducing the amount of reader energy. It could be a passive device. This would decrease the amount of energy available for reading other normal tags.

• An attacker can remove or physically destroy tags attached to objects. This is used by an attacker to avoid tracking. A thief destroys the tag to remove merchandise without detection.

• An attacker shields the tag from being read with a Faraday Cage. A Faraday Cage is a metal enclosure such as a bag lined with aluminum foil that prevents the reader from reading the tag. For E-passport, it has been suggested that it should be inserted into a foil holder to prevent this type of attack.

• An attacker with powerful reader can also jam the reader by creating a more powerful return signal than the signal returned from the tags and thus making the system unavailable to authorized users.

• An attacker performs a traditional Internet denial-of-service attack against the servers gathering EPC numbers from the readers and also against ONS.

• An attacker sends URL queries to a database causing it to do database queries and therefore denying access to authorized users.

It happens when an unprivileged user or attacker gains higher privileges in the system than what they are authorized.

• A user logging on to the database to determine product information can become an attacker by raising his/her status in the information system from a user to a root server administrator and write or add malicious data into the system.

This solution was proposed by the Auto-ID Center and EPC global. In this scheme, each tag has a unique password, for example of 24 bits, which is programmed at the time of manufacture. Upon receiving the correct password, the tag will deactivate forever.

We can protect the privacy of objects labeled with RFID tags by isolating them from any kind of electromagnetic waves. This can be done by using what is known as a Faraday Cage (FC), a container made of metal mesh or foil that is impenetrable by radio signals. Currently, there are a number of companies that sell this type of solution.

Another way of obtaining isolation from electromagnetic waves is by disturbing the radio channel, a method which is known as active jamming of RF signals. This can also used as an alternative to the FC approach. This disturbance may be done with a device that actively broadcasts radio signals, so as to completely disrupt the radio channel, thus preventing the normal operation of RFID readers.

When more than one tag answers a query sent by a reader, it detects a collision. The most important singulation protocols are ALOHA (13.56 MHz) and the tree-walking protocol (915 MHz). Juels used this feature to propose a passive jamming approach based on the tree-walking singulation protocol, called blocker tag which simulates the full spectrum of possible serial numbers for tags.

RFID Bill of Rights, proposed by Garfinkel, should be upheld when using RFID systems. He does not try to turn these rights into Law, but to offer it as a framework that companies voluntarily and publicly should adopt.

In 2003, Kinoshita proposed an anonymous-ID scheme. The fundamental idea of the proposal is to store an anonymous ID, E(ID), of each tag, so that an adversary can not know the real ID of the tag. E may represent a public or a symmetric key encryption algorithm, or a random value linked to the tag ID. In order to solve the tracking problem, the anonymous ID stored in the tag must be renewed by re-encryption as frequently as possible.

This is based on a simple two way challenge-response algorithm. It is proposed by Feldhofer. But the problem with this approach is that it requires having AES implemented in an RFID tag.

There are solutions that use public-key encryption, based on the cryptographic principle of re-encryption. The reader interested in the precise details can read the paper of Juels.

One of the most commonly used proposals for solving the security problems in the RFID technology is the use of hash functions.

Weis proposed this simple security scheme. It bases on one-way hash functions. Each tag has a portion of memory reserved to store a temporary Meta ID and perates in either a locked or an unlocked state. The reader hashes a key k for each tag, and each tag holds a metaID (metaID = hash (k)). While locked, a tag answers all queries with his metaID and offers no other functionality. To unlock a tag, the owner queries the backend database with the metaID from the tag, looks up the appropriate key and sends the key to the tag. The tag hashes the key and compares it to the stored metaID.

One of the problems of hask lock scheme solution is that it allows the tracking of individuals. For avoiding this, the metaID should be changed repeatedly in an unpredictable way. So, Weis proposed an extension of the hash lock scheme. It requires that tags have a hash function and a pseudo-random number generator.

Ohkubo proposed a list of points that must be satisfied in all security designs of RFID schemes: keep complete user privacy, eliminate the need for extraneous rewrites of the tag information, minimize the tag cost, eliminate the need for high power of computing units, and provide forward security. In hash-chain scheme,two hash functions (G and H) are embedded in the tag.

For mutual authentication between tags and readers, Molar suggested a scheme with privacy for the tag. This protocol uses a shared secret s and a Pseudo Random Function (PRF) to protect the messages exchanged between the tag and the reader.

In the hash schemes, the load of the server (for identifying tags) is proportional to the number of tags which is one of the main drawbacks of the scheme. For eliminating this, Molnar has proposed a new scheme which will reduce this load. It is named Tree-Based Private Authentication. This new protocol reduces the load to O (log n) but introduces the use of a Trust Center (TC). Another interesting proposal is the work of Gildas and Oechslin, where a time-space trade-off is proposed.

Weis introduced a new concept of human computer authentication protocol due to Hopper and Blum, adaptable to low-cost RFIDs. This concept has been recently extended in an article by Weis and Juels, where they propose a lightweight symmetric-key authentication protocol named HB+. The security of both the HB and the HB+ protocols is based on the Learning Parity with Noise Problem, whose hardness over random instances still remains as an open question.

There are some solutions which do not use true cryptographic operations. So a set of extremely-lightweight challenge-response authentication protocols have been proposed. These protocols can be used for authenticating tags, but they can be broken by a powerful adversary. Juels proposed a solution based on pseudonyms without using hash functions at all. The RFID tags store a short list of random identifiers or pseudonyms (known by authorized verifiers to be equivalent). When tag is queried, it emits the next pseudonym in the list.

The difficulty of factorizing large numbers that have 2 and only 2 factors i.e. Prime numbers is the main basic of RSA algorithm. It works on a public and private key system. The public key is made available to everyone. With this public key, a user can easily encrypt the data but cannot decrypt it. The person, who can only decrypt it, is the one who possesses the private key. Though it is theoretically possible, it is extremely difficult to generate the private key from the public key. This makes the RSA algorithm a very popular choice in data encryption.

The RSA public key algorithm was first published in the paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystems in 1977 by MIT professors Ron Rivest, Adi Shamir and Len Adleman. It is also named after the initials of their surnames. In the September 1977 issue of The Scientific American, the paper was first published. The authors offered to send their full report to anyone who sent them a self-addressed stamped envelope. But, the NSA (National Security agency) did not like the idea of distributing the cryptography source code internationally and requested that it be stopped. However the distribution continued when the NSA failed to provide a legal basis for their request. Later in The Communications of the ACM (Association for Computing Machinery) the following year the algorithm was published.

First, a key set is generated i.e. a private key, a public key, and a modulus. The encoded information using the public key (and modulus) can be decoded only using the private key (and modulus). Similarly, information encoded using the private key (and modulus) can only be decoded by using the public key (and modulus).

The main steps involved in generating the key set are described below:-

(1) Find two large prime numbers: p & q

[A prime number is the number which has no factors other than itself and 1 for example 5 or 25771.]

(2) Let the modulus, n= p * q.

(3) Let c = (p-1)*(q-1). c called the quotient is always even.

(4) Choose a private key number e, less than n, such that e & c have no common factors (are relatively prime)

(5) The public key d = e^ (-1) mod c (that is, d*e mod c = 1)

[We could first choose the public key e, and then the private key would be d.]

In step 5, the word "mod” means that modulo arithmetic is used for example, a clock. If we start at 9 o'clock, and add 8 hours (eight hours later), we get 5 o'clock, not 17 o'clock; the numbers "wrap around". We write this example addition as 9 + 8 mod 12 = 5. Multiplication works similarly in modulo arithmetic. We can subtract off the modulus as many times as necessary until the result is less than the modulus, if result is bigger than the modulus. So 7 * 5 mod 12 = 11 (that is, 7*5 mod 12 = 35 mod 12 = 12*2+11 mod 12 = 11)

For encoding a message, we convert some number m, then the secret s = m ^ d mod n (that means m raised to the d power, modulo n) and to decode the secret the message m = s ^ e mod n.

It is very difficult to figure out how to factor it into p & q as long as n is so longer. So it is impossible to find out the secret key e from the public key d and modulus n.

Here is an example using very small numbers.

Say, we choose two primes as p = 3, q = 11. Then the quotient, c = (3-1)*(11-1) = 20. .

Now, we choose the private key, e = 7, then the public key would be d = 3 because e*d mod c = 7*3 mod 20 = 21 mod 20 = 1, and the modulus is n = p*q = 3*11 = 33.

(But with this small modulus, our message must be broken into pieces small enough to represent with a number less than 33, so we could do one letter at a time.)

Suppose the secret message is the letter "P", which we could write as the number 16 (since P is the 16th letter in the alphabet), m = 16.

Then the encoded secret is

s = m^d mod n = 16^3 mod 33 = 4096 mod 33 = 33*124+4 mod 33 = 4 and to decode the secret again m = s^e mod n = 4^7 mod 33 = 16384 mod 33 = 33*496+16 mod 33 = 16 which gives us back the original message: 16 (or "P").

(There are some techniques of raising numbers to powers in modulo arithmetic that avoid calculating vary large numbers.)

In the public-key cryptosystem, a user can digitally "sign" a message they send. This digital signature provides proof that the message originated from the designated sender. For more effective, digital signature needs to be both message-dependent as well as signer-dependent. This helps us to prevent electronic "cutting and pasting" as well as modification of the original message by the recipient.

Suppose user A wanted to send a "digitally-signed" message, M, to user B:

User B cannot alter the original message or use the signature with any other message. For doing that, it requires user B to know how to decrypt a message using A's decryption procedure.

Euler's Theorem is the central mathematical theorem behind the RSA algorithm.

If n is a positive integer and m is an integer that is relatively prime to n, then

m^c mod n = 1 , where c is the number of positive integers less than n that are relatively prime to n. Prime means the two numbers have no positive factors in common ,other than 1, for example 12 and 25 are relatively prime. One name for c above is the totient of n or the Euler Phi function of n.

For the RSA algorithm, n=p*q where p & q are prime numbers. Then the numbers less than n that have common factors are the multiples of p (q-1 of them) and the multiples of q (p-1 of them). So the totient of n includes all the rest:-

c = (n-1) - (q-1) - (p-1) = p*q - p - q + 1 = (p-1)*(q-1).

Then with the two keys e & d chosen so that e*d mod c = 1, then e*d = c*k + 1 for some number k.

Given a message number m, then the secret number s is s = m^d mod n and so to decode we find

s^e mod n = (m^d)^e mod n = m^(d*e) mod n = m^(c*k+1) mod n = (m^c)^k * m^1 mod n = 1^k * m mod n = 1*m mod n = m ,because m^c mod n = 1 by Euler's Theorem. Actually, Euler's Theorem only applies if m is relatively prime to n, but it can be shown that this still works in that case due to other theorems.

Presently, the RSA system is used compressively in a wide variety of products, platforms, and industries around the world. It is also used in various commercial software products and is planned to be in many more. Currently the RSA algorithm is built into the operating systems by Microsoft, Apple, Sun, and Novell. In hardware, the RSA algorithm is found in secure telephones, on Ethernet network cards, and on smart cards. Additionly, the algorithm is incorporated into all of the major protocols for secure Internet communications, including S/MIME, SSL, and S/WAN. Also, internally it is used internally in many institutions, like branches of the U.S. government, major corporations, national laboratories, and universities.

At present time, technology using the RSA algorithm is licensed by over 700 companies. The estimated installed base of RSA BSAFE encryption technologies (RSA BSAFE Encryption, Signature and Privacy solutions are the most widely used e-security technology in the world) is around 500 million. The majority of these implementations include use of the RSA algorithm, making it by far the most widely used public-key cryptosystem in the world. This figure is expected to grow rapidly as the Internet and the World Wide Web expand.

We provide a professional essay writing service that thousands of our customers use as an effective way of improving their grades, improving their research and saving them lots of time.

Order Now. It takes less than 2 minutes.

  1.  
  2.  
  3.  
  1.  
Live Chat

Essay, dissertation & assignment
prices

About UK Essays

Buying an essay?
All you
need to
know...

Bibliography & References

SAVE Yourself Time & Money

Save £££s with our great
bundle
deals

Free
Essay
Questions

Harvard Referencing
Generator

Sign up and be the first to receive our latest offers:

Over 5000 words? Get 5-10 percent off!