View Full Version : Sistemul De Acces Conditionat!
In curand il incep si pe asta. :D
Scrambling of the services. The digitized broadcasting stream, called a transport stream (TS), is applied to the scrambler. It contains an algorithm that is designed to minimize the likelihood of a pirate attack. The output of the scrambler is applied to the distribution medium such as cable, satellite or terrestrial, for delivery to the end user. The descrambling key is recovered from the encrypted keys within the scrambled TS by the smart card, and it is applied to a matching de-scrambling algorithm to recover the original program content.
Encryption and decryption of keys. The CA system generates the control word (CW) for the scrambler and also generates and encrypts special CA messages, namely entitlement control messages (ECMs) and entitlement management messages (EMMs). These are used in conjunction with the entitlements stored on the smart card to recover the CW for descrambling the TS.
ECMs are related to the program content at a given time and are used for recovering the control word. The CA sub-system in the set-top box (STB) decrypts the control word only when authorized to do so, and that authority is sent to the STB in the form of an EMM. EMMs thus convey information related to the status of the subscription, and this layered approach is fundamental to the operation of all CA systems in use today.
Another part of the CA system stores smart card information in a database, and a smart card management system provides it with information on smart cards that have been processed for use in the pay-media operation.
An interface to a Subscriber Management System (SMS). The SMS contains a database of all subscribers in the pay-media network. It is capable of performing accounting operations on this data as well as issuing commands to the CA system to enable or disable services for subscribers.
Services supported by CA systems
Most CA systems support methods for authorizing several types of services for subscribers. The most common variants are standard subscription, pay per view (PPV), impulse pay per view (IPPV), video on demand (VOD) and near video on demand (NVOD).
End-user terminals
A low-cost consumer STB for terrestrial or cable networks, or an integrated receiver decoder (IRD) for satellite networks, together with a secure CA device such as a smart card, is key to the provision of pay-media services to the subscriber. The function of the secure CA device in the STB is to verify access rights and security levels, so tight integration between the CA system and the STB is required. Advanced STBs require their middleware to be integrated with the CA system, and STBs are also able to support other secure features such as software downloads and STB/smart card linkages.
Piracy resistance
Signal theft and pay-media piracy is a business that companies involved in conditional access must deal with continually. Effective piracy management is based on three principles: secure technology, legal measures and commercial measures. Secure technology involves the deployment of state-of-the-art technology with built-in electronic counter-measures, and the endorsement of that technology by external auditors.
Legal measures involve detection through surveillance and Internet monitoring, prosecutions through law enforcement agencies, participation in security-related bodies on national, international and global levels, and support of the development of relevant legislation. Commercial measures involve frustrating the supply of components to the pirate community and the distribution of the finished products.
CA system interoperability
Due to historical factors or regulatory requirements, service providers sometimes have a need for deploying different CA systems in the same network. In other cases, perhaps to keep STB costs low, different operators agree on one CA system but desire independence in the control and management of their subscribers. A number of solutions for ensuring the interoperability of CA systems under these conditions have been successfully deployed.
All pay-media operators require a means for ensuring that payment is received in return for the program content they provide. The technical system that achieves this objective is called a conditional-access (CA) system.
Two key functions of CA systems are to exercise control over the access to a service that is transmitted electronically, and to control the conditions under which access is granted. There are various reasons for implementing a CA system, such as the need to enforce payment by the end user for consumed services, to restrict access to programming in a particular geographical area because of program rights considerations or to facilitate parental control.
RSA ALGORITHM:
RSA-based Cryptographic Schemes
The RSA algorithm was invented by Ronald L. Rivest, Adi Shamir, and Leonard Adleman in 1977. There are a variety of different cryptographic schemes and protocols based on the RSA algorithm in products all over the world; RSA Laboratories recommends the RSAES-OAEP encryption scheme and the RSASSA-PSS signature scheme with appendix for new applications.
RSAES-OAEP (RSA Encryption Scheme - Optimal Asymmetric Encryption Padding) is a public-key encryption scheme combining the RSA algorithm with the OAEP method. The inventors of OAEP are Mihir Bellare and Phillip Rogaway, with enhancements by Don B. Johnson and Stephen M. Matyas.
RSASSA-PSS (RSA Signature Scheme with Appendix - Probabilistic Signature Scheme) is an asymmetric signature scheme with appendix combining the RSA algorithm with the PSS encoding method. The inventors of the PSS encoding method are Mihir Bellare and Phillip Rogaway. During efforts to adopt RSASSA-PSS into the P1363a standards effort, certain adaptations to the original version of RSA-PSS were made by Bellare and Rogaway and also by Burt Kaliski (the editor of IEEE P1363a) to facilitate implementation and integration into existing protocols.
CSA Overview
The CSA is shown in the following 2 figures:
http://img216.imageshack.us/img216/4663/overviewfig4engifxg3.gif
and
http://img216.imageshack.us/img216/3263/overview2fig3engifpk8.gif
The overview figure show a block diagram of a CSA descrambler which is a combination of 2 cryptographic algorithms: a stream and a block cipher.
A CSA scrambler could look like this:
http://img216.imageshack.us/img216/3079/csascramblerne0.gif
Stream Cipher Overview
http://img216.imageshack.us/img216/1806/streamcipherfig5engifsh6.gif
Block Cypher Overview
http://img216.imageshack.us/img216/8590/blockcipherfig6enwa0.jpg
The following list of technical terms often used in discussions on the
tv-crypt mailing list is intended to help newcomers getting started
quickly and hopefully will also provide for more efficient
communication and less misunderstandings. If you don't understand any
term or abbreviation in a tv-crypt contribution, just do a fulltext
search over this text with your editor.
Any additions and suggestions for improvement are very welcome.
Below follows also a list of recommended introductory literature.
ATR
The Answer-To-Reset message is the first reaction of a smart card
after a reset strobe. The format is specified in ISO 7816.
ASIC
An Application Specific Integrated Circuit is a chip that has been
produced for one specific customer according to his specifications
by a semiconductor manufacturer. In order to keep mask design costs
low, ASICs are usually based on gate arrays, i.e. chips with a large
number of standard cells that are connected by an aluminum path
layer designed specifically for one customer.
blocker
A device inserted between a card and a decoder that checks the data
traffic and interrupts or modifies data packets whenever a card
deactivation message is about to be sent to the card in order to
avoid the deactivation of unsubscribed cards.
BSkyB
British Sky Broadcasting, a TV broadcasting company for the British
and Irish market, belonging to News Corporation, Ruppert Murdoch's
global media empire.
card
A detachable cryptographic module that can be inserted into a pay-TV
decoder, usually conforming to the form factors described in the ISO
7816 or PCMCIA standards, sometimes also in other forms (e.g. the
Nagravision card is formed like a small plastic key). Cards contain
special smart card security processors with a few hundred bytes of
RAM and a few kilobytes of ROM and EEPROM, and sometimes also
additional chips with cryptographic functions.
CM
A Counter Measure is any action taken by the operator of a pay-TV
access control system in order to render clone devices ineffective,
e.g. by using alternative keys in the cards or by exploiting
incompatibilities in the clone software. Especially the nanocommand
interpreters of BSkyB 09 clones have been highly non-portable and
allowed NDC to design a large number of counter measures.
CW
A Control Word is the data used to generate the seed value for the
PRNG that determines the cut-point coordinates for the next approx.
10 s in the EuroCrypt system. In VideoCrypt, the data of the 0x78
instruction corresponds to the CW, which is there changed every 2.5
seconds.
Dallas
The DS5002FP is a 8051 compatible microcontroller from Dallas
Semiconductors designed for highest security applications. It keeps
its software in encrypted form in external battery buffered SRAM and
encrypts each single RAM access. The DS5002FPM version is designed
to be especially resistant against EBT analysis. The DS5000 is the
predecessor of the DS5002FP.
EBT
An Electron Beam Tester is a special modified scanning electron
microscope (SEM) that examines the electrons reflected from a chip
surface in order to determine the voltages on the chip. EBTs can
visualize logic states of on-chip connections as different grey
values (voltage contrast imaging). EBTs are probably a very powerful
tools for analyzing security processors, but they are very expensive
devices.
ECM
An Entitlement Control Message used in EuroCrypt contains the CW
encrypted with an operation key SK. In John McCormac's Black Book,
ECM also means Electronic Counter Measure (see CM).
EMM
An Entitlement Management Message transfers a new operation key SK
to a EuroCrypt smartcard that will allow to decrypt further ECMs.
EMMs can be encrypted using the service management key PDK or the
issuer key IK.
ETSI
European Telecommunication Standards Institute, a company that sells
incredibly expensive paper, including the D2MAC and DVB standards.
EuroCrypt
A pay-TV access control system for the D2MAC color TV broadcasting
system that has been standardized by CENELEC in the European
Standard EN 50094.
FIB
A focused ion beam workstation is an extremely powerful tool to
manipulate VLSI circuits. It can remove and deposit material on
chip surfaces with very high resolution. FIBs can be used to
rewire circuits in chips. They cost several million USD, however
they can be rented for comparatively little money.
hash function
Any function that maps a large set of values onto a much smaller set
of values. Good hash functions have the property that all possible
result values are equally likely. Hash functions are commonly used
in order to store and retrieve data efficiently. Checksums for
example are typical hash functions. Cryptographic hash functions
(also known as message digest algorithms or one-way hash functions)
have the property that it is a very difficult problem to find an
input value that produces a given hash result. Well known
cryptographic hash functions are for example SHS and MD5. In
VideoCrypt, the 32 data bytes of the 0x74 instruction serve as input
to a secret cryptographic hash function; the hash result can be
fetched from the card with using the 0x78 instruction. The
cryptographic hash function implemented in a VideoCrypt smartcard has
in addition a property common with an encryption function: It is
designed such that it is a very difficult problem to guess the
algorithm that implements the hash function by examining a large
number of input/output pairs.
ICC analysis
ICC is the current in the VCC connection of a security processor.
ICC depends on the internal events in a processor and it might be
possible to learn more about the executed algorithm by observing ICC
with digital storage oscilloscopes.
instruction
This term usually refers to a ISO 7816 data packet sent or requested
by a decoder. The instruction number INS is the second byte of the
5-byte long ISO 7816 header.
ISO
International Standards Organization, another company that sells
even more expensive paper, including the MPEG digital TV compression
and ISO 7816 chip card standards. Address: ISO, Case postale 56,
CH-1211 Geneve 20, Switzerland, phone +41 22 749 01 11, fax +41 22
733 34 30. See also <www.iso.ch>.
ISO 7816
The standard to which all cards used today in common pay-TV access
control systems conform at least partially. ISO 7816 defines the
physical form of the card, the location of the eight contacts (VCC,
GND, I/O, CLK, RST, VPP, C4, C8), the electrical characteristics of
the contact interface, the answer to reset (ATR) and protocol
selection mechanisms, and several generic command and data
transmission protocols. EuroCrypt and VideoCrypt use the T=0
protocol of ISO 7816.
ISO header
This refers to the 5-byte header of the T=0 protocol specified in
ISO 7816-3. The five bytes are referred to as CLA, INS, P1, P2, P3.
key
A sequence of bits used as a parameter to cryptographic algorithms.
laser cutter
A laser with a special optic and control unit that can be attached
to microscopes or microprobers. Laser cutters can be used for
micrometer-resolution manipulations on VLSI chips such as local
removal of the passivation layer or the interruption of metal
interconnections.
LFSR
A Linear Feedback Shift Register is probably the form of PRNG that
can most easily be implemented in hardware. It is a simple shift
register where the next input value is always the parity bit (= XOR
result) of certain shift register bits. A shift register that
delivers an input to the XOR is called a tap. The selection of taps
used in a particular LFSR is commonly written as a polynomial over
x, with coefficients one for taps and coefficients zero for other
shift register bits. The degree of the polynomial indicates the
length of the LFSR. Factorizing this polynomial allows to determine
the length of the pseudo random bit sequence generated by the LFSR.
A primitive polynomial corresponds to a LFSR with maximal sequence
length. The output bit of a LFSR is the bit shifted out of the
register. This usual form of the LFSR is known as Fibonacci
configuration. An alternative LFSR form known as Galois
configuration has XOR elements located between certain shift
register bit flip-flops and XORs certain shifted bits with the
output bit. LFSRs alone are extremely bad cryptographic PRNGs,
because the Berlekamp-Massey algorithm can crack them very easily.
However, good cryptographic PRNGs can be constructed using a
combination of several LFSRs that influence each other.
microprober
A special optical microscope and a set of very fine needles that
can be used to contact the metal interconnection layer of
VLSI circuits. This is the most frequently used tool to extract
software stored in EEPROM security microcontrolers. It can be used
to interfere with instruction processing and to eavesdrop on-chip bus
lines. One manufacturer of microprobers is Karl Suss KG in Munich.
nanocommand
In a subcommand 0x80 received by a BSkyB 09 card, the 16 data bytes
before the final 5 signature and checksum bytes contained tiny
programs in a special interpreter language. The bytes of these
programs are known as nanocommands. The nano-opcodes were simply
jump vectors into a quite obscure EEPROM area of the BSkyB 09 card.
Some nanocommands allowed to extend the hash function, others
allowed write access to EEPROM and RAM that could affect the
interpretation of later nanocommands. Nanocommands proofed to be an
efficient means for allowing many counter measures.
NDC
News Datacom Ltd, the company that developed the VideoCrypt and
VideoGuard pay-TV access control systems and other security
applications. NDC is owned by Ruppert Murdoch's News Corporation and
has headquarters in Maidenhead near London and research and
development laboratories in Jerusalem, Israel. News Datacom has now
changed its name into NDS.
PIC
The PIC16C84 and other low-cost microcontrollers as well as serial
EEPROMs are produced by Microchip Technology Inc.
PGP
Pretty Good Privacy is a very popular e-mail encryption and
autentication tool developed by Phil Zimmermann and used very
frequently by tv-crypt members to exchange confidential information
over the Internet.
Phoenix
A PC software developed in early July 1994 by tv-crypt members that
emulates the card interface of a decoder and allowed to send faked
card and channel activation messages to genuine BSkyB series 09
cards.
PPV
A Pay Per View mechanism allows a broadcaster to charge viewers
not only for a permanent subscription to a set of channels,
but also for the access to special single broadcasts like a
spectacular boxing massacre.
PRNG
A Pseudo Random Number Generator is an algorithm that produces a
sequence of numbers that are usually uniformly distributed over a
given range and that show no obvious statistical dependency with
each other. A pseudo random number has an internal state that
changes with each produced random number. Each generated random
number is a function of the internal state. The set of possible
internal states is usually much larger than the set of possible
output numbers. The initial state of a PRNG is called the seed
value. A cryptographic PRNG has the property that if a long sequence
of random numbers produced by the PRNG is know, it is a very
difficult problem to determine the internal state, the seed value or
one of the next output numbers, even if the algorithm is completely
known.
Season7
A PC software that can emulate a VideoCrypt smart card. By using a
serial-port to ISO 7816 adapter, this software allowes to watch
VideoCrypt programs with a normal VideoCrypt decoder, but without a
VideoCrypt subscription card. The first version was released by
Markus Kuhn in early April 1994 to around 10 people who participated
in technical discussions about VideoCrypt in the old
alt.satellite.tv.europe USENET group. This group of people became
the first tv-crypt members. Later, others took the software,
extended and upgraded it or modified it heavily for EuroCrypt
emulation and published it under various names like Season7a,
Season9, MACcess, Voyager, etc. OMIGOD was a nickname for Season7
used in Hack-Watch by John McCormac. The name refers to the original
motivation for writing the software: allowing the author to watch
the seventh season of Star Trek episodes on BSkyB.
seed value
The initial internal state of a PRNG. The seed value sent to the
PRNG implemented in the PTV-3 chip in each VideoCrypt decoder is
calculated by the Motorola 68705R3 processor using the 8-byte hash
result (control word) fetched from the smart card using the 0x78
instruction.
SEM
A Scanning Electron Microscope uses electron beams instead of light
in order to provide very large magnification factors.
signature
A digital signature is the part of a data packet that proves to the
receiver that the data packet was prepared by an authorized source
and has not been created or modified by a hacker. Digital signatures
are usually based on the result of a cryptographic hash function.
subcommand
This fourth byte of the 32 data bytes in a 0x74 instruction
indicated to the series 07 and 09 BSkyB cards a command that was to
be executed. Example subcommands are the activation or deactivation
of certain channels or of the whole card as well as counter measure
subcommands that execute highly non-portable and difficult to
understand code. The subcommand byte was XORed with a value
calculated from the previous data bytes using a very simple XOR and
rotate algorithm. Subcommand 0x80 contained up to 16 nanocommands.
Syster Nagravision
A pay-TV access control system for the PAL color TV broadcasting
system developed by Nagra Kudelski of Switzerland and manufactured
by Eurodec/SAGEM. Syster Nagravision is used by Canal Plus, Canal
Plus Espagna, Premiere, and Teleclub.
token
In a PPV mechanism the access code for one PPV event.
VBL
A VideoCrypt Broadcast Logfile contains a recording of all 0x74
instructions sent to the card during one TV event. The data format
of VBL files is very similar to VCL files. VBL files allow to submit
to the owner of a genuine card the data necessary to create a VCL
file even if the owner of the genuine card has missed the broadcast
of the program from which a VCL file should be produced.
VCL
A VideoCrypt Card Logfile contains all information necessary in
order to allow a VideoCrypt card emulator to respond like a genuine
card to the instruction 0x78 hash value requests of the decoder. The
VCL file format is specified in the file details.txt of Season7. VCL
files allow the delayed data transfer hack: a person without a
genuine VideoCrypt card records the encrypted broadcast of a program
on a VCR, downloads later from the Internet a published VCL file for
this program, and decrypts it while playing the VCR recording to the
decoder.
VCR
Video Cassette Recorder, a magnetic tape recorder for TV signals.
VideoCrypt
A pay-TV access control system developed by NDC for the PAL color TV
broadcasting system used by BSkyB, The Adult Channel, BOB, Sky TV
New Zealand, and a few other channels. Described by european patent
application 0 428 252 A2.
VideoGuard
A pay-TV access control system developed by NDC for the Huges
DirecTV digital satellite broadcasting system (DSS) in the US. DSS
and VideoGuard are technically similar to DVB and MPEG-2, but not
compatible.
RSA ALGORITHM:
http://www.zshare.net/download/570418455849ac14/
-e doar un intro, aplicarea unor teoreme celebre(din teoria numerelor,apoi teoreme din cryptografie),ce duce la creearea mai tarziu a ce numim noi in final The RSA ALGORITHM :D(vine si... restul)
Answer to Reset - Basics
The "Answer to Reset" is the first information sended by the card to the card reader after reset initiated by reader. It is a simple row of parameter, in which the card is telling the reader, how to communicate with it. The structure of ATR Contact cards, regardless wether processor chip card or memory chip card, independent of used protocol. all the same. But the content depends on the specification, the chip structure and manufacturer guidelines. Smart card manufacturers have the possibility to control the performance of the chip card, by defining the parameters in the ATR. Chip cards can have more ATRs, to reach more compatibility.
The structure of an ATR consists of several blocks, the Initial Charater, Format Character, Interface Characters, Historical Bytes and the Check Caracter.
The Initial Character, called TS, is used for defining the Bit-Coding (logical „1“ is transmitted as Low (L) or High (H)) and for recognition of the factor relevant for bit-length, used by the card. This is implemented as follows, the start-bit and the next three bits are always built on the pattern (L) H H L x x x x x x (L = Low, H = High, x = don’t care). The card reader is measuring the time between the two falling edges, and divides it by three. The resulting Elementary Time Unit (etu) is defining the die lenght of time of one bit.
The next three bits of the sequence indicate the bit-coding. Three bits on high means that logic "1" is coded as "High" (direct converting); three bits on low means, logic 0 is coded as Low (indirect converting). first Bit: Start-Bit; last Bit: Partity-Bit
Direct Conversion - (L) H H L H H H L L (H)
Indirect Conversion - (L) H H L L L L L L (H)
Consider, that, depending on the conversion, the order sequence is changing. Direct conversion means that the "Least signigicant Bit is transmitted first, otherwise the Most Significant Bit is transmitted first when indirect conversion is used.
Because Interface Characters and Historical Characters are optional, the Format Caracter (called T0) indicates, which characters are transmitted. The Most Signifiant Nibble (MSN) of T0 is showing by its bits, which of the next four Interface Characters are transmitted. The Least Significant Nibble (LSN) is interpreted as number and indicates the number of Historical Characters (1 to 15). Next table is showing possible Format Characters.
http://www.cryptoshop.com/en/images/pcs_spacer.gif
Format Character
b8 b7 b6 b5 b4 b3 b2 b1
- - - - x x x x number of historical characters - - - 1 - - - - TA(1) is transmitted - - 1 - - - - - TB(1) is transmitted - 1 - - - - - - TC(1) is transmitted 1 - - - - - - - TD(1) is transmitted http://www.cryptoshop.com/en/images/pcs_shadow_top_right.gif http://www.cryptoshop.com/en/images/pcs_shadow_bottom_left.gif http://www.cryptoshop.com/en/images/pcs_spacer.gif http://www.cryptoshop.com/en/images/pcs_spacer.gif http://www.cryptoshop.com/en/images/pcs_shadow_bottom_right.gif
The structure of the Interface Characters can be compare to chained lists. TD(1) is showing, like T0, in its MSN (Most Significant Nibble), which of the following Interface Characters (TX(i+1), X I {A, B, C, D}, i > 1) appears in the ATR. The Least Significant Nibble (LSN) of TD(i) indicates the protocol-type to be used (T = 0, T = 1 resp. others (in future). If the chip card is supporting more protocols, this is shown in TD(i+1) then the selection of the protocol has to be done in a separate workflow. TA(1), TB(1), TC(1) and TB(2) are calle global Interface Bytes. They are telling the card reader the internal clock pulse, the necessary programming voltage and the resulting programming power. The interpretation of TA(i), TB(i), TC(i) (i > 2) depends on the protocol type.
The content of the Historical Bytes isn't standardized yet. You will find informations about the card manufacturer or issuer, the card type, versionnumbers and state of the card. In austrian maestro cards you will also find the balance of the integrated austrian E-Purse "Quick", in this bytes.
By using the Check Character an additional Parity-check can be done. The Check Character contains check byte for the ATR - XOR from T0 to the last byte before TCK. Its transmittance depends on certain criteria, e.g. the protocol type, therefore, such an parity check isn't possible in all situations.
http://www.cryptoshop.com/en/images/atraufbau.jpgATR-schema
-despre RSA algorithm si incepem cu inceputul:
Key Generation Algorithm
Generate two large random primes, p and q, of approximately equal size such that their product n = pq is of the required bit length, e.g. 1024 bits
Compute n = pq and (φ) phi = (p-1)(q-1).
Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1
Compute the secret exponent d, 1 < d < phi, such that ed ≡ 1
The public key is (n, e) and the private key is (n, d). Keep all the values d, p, q and phi secret.
n is known as the modulus.
e is known as the public exponent or encryption exponent or just the exponent.
d is known as the secret exponent or decryption exponent.
Encryption
Sender A does the following:-
Obtains the recipient B's public key (n, e).
Represents the plaintext message as a positive integer m
Computes the ciphertext c = me mod n.
Sends the ciphertext c to B.
Decryption
Recipient B does the following:-
Uses his private key (n, d) to compute m = cd mod n.
Extracts the plaintext from the message representative m.
Digital signing
Sender A does the following:-
Creates a message digest of the information to be sent.
Represents this digest as an integer m between 0 and n-1.
Uses her private key (n, d) to compute the signature s = md mod n.
Sends this signature s to the recipient, B.
Signature verification
Recipient B does the following:-
Uses sender A's public key (n, e) to compute integer v = se mod n.
Extracts the message digest from this integer.
Independently computes the message digest of the information that has been signed.
If both message digests are identical, the signature is valid.
Summary of RSA
n = pq, where p and q are distinct primes.
phi, φ = (p-1)(q-1)
e < n such that gcd(e, phi)=1
d = e-1 mod phi.
c = me mod n, 1<m<n.
m = cd mod n.
Key length
When we talk about the key length of an RSA key, we are referring to the length of the modulus, n, in bits. The minimum recommended key length for a secure RSA transmission is currently 1024 bits. A key length of 512 bits is now no longer considered secure, although cracking it is still not a trivial task for the likes of you and me. The longer your information is needed to be kept secure, the longer the key you should use. Keep up to date with the latest recommendations in the security journals.
There is small one area of confusion in defining the key length. One convention is that the key length is the position of the most significant bit in n that has value '1', where the least significant bit is at position 1. Equivalently, key length = ceiling(log2(n+1)). The other convention, sometimes used, is that the key length is the number of bytes needed to store n multiplied by eight, i.e. ceiling(log256(n+1)).
The key used in the RSA Example paper s an example. In hex form the modulus is 0A 66 79 1D C6 98 81 68 DE 7A B7 74 19 BB 7F B0
C0 01 C6 27 10 27 00 75 14 29 42 E1 9A 8D 8C 51
D0 53 B3 E3 78 2A 1D E5 DC 5A F4 EB E9 94 68 17
01 14 A1 DF E6 7C DC 9A 9A F5 5D 65 56 20 BB AB
The most significant byte 0x0A in binary is 00001010'B. The most significant bit is at position 508, so its key length is 508 bits. On the other hand, this value needs 64 bytes to store it, so the key length could also be referred to by some as 64 x 8 = 512 bits. We prefer the former method. You can get into difficulties with the X9.31 method for signatures if you use the latter convention.
Computational Efficiency and the Chinese Remainder Theorem (CRT)
Key generation is only carried out occasionally and so computational efficiency is less of an issue.
The calculation a = be mod n is known as modular exponentiation and one efficient method to carry this out on a computer is the binary left-to-right method. To solve y = x^e mod n let e be represented in base 2 as
e = e(k-1)e(k-2)...e(1)e(0)
where e(k-1) is the most significant non-zero bit and bit e(0) the least.
set y = x
for bit j = k - 2 downto 0
begin
y = y * y mod n /* square */
if e(j) == 1 then
y = y * x mod n /* multiply */
end
return y
The time to carry out modular exponentation increases with the number of bits set to one in the exponent e. For encryption, an appropriate choice of e can reduce the computational effort required to carry out the computation of c = me mod n. Popular choices like 3, 17 and 65537 are all primes with only two bits set: 3 = 0011'B, 17 = 0x11, 65537 = 0x10001.
The bits in the decryption exponent d, however, will not be so convenient and so decryption using the standard method of modular exponentiation will take longer than encryption. Don't make the mistake of trying to contrive a small value for d; it is not secure.
An alternative method of representing the private key uses the Chinese Remainder Theorem (CRT). The private key is represented as a quintuple (p, q, dP, dQ, and qInv), where p and q are prime factors of n, dP and dQ are known as the CRT exponents, and qInv is the CRT coefficient. The CRT method of decryption is four times faster overall than calculating m = cd mod n. For more details, see [PKCS1 (http://www.di-mgt.com.au/rsa_alg.html#PKCS1)]. The extra values for the private key are:-
dP = (1/e) mod (p-1)
dQ = (1/e) mod (q-1)
qInv = (1/q) mod p where p > q
These are pre-computed and saved along with p and q as the private key. To compute the message m given c do the following:-
m1 = c^dP mod p
m2 = c^dQ mod q
h = qInv(m1 - m2) mod p
m = m2 + hq
Even though there are more steps in this procedure, the modular exponentation to be carried out uses much shorter exponents and so it is less expensive overall.
Someone has pointed out that most large integer packages will fail when computing h if m1 < m2. This can be easily fixed by computing h = qInv(m1 + p - m2) mod p or, alternatively, as we do it in our BigDigits implementation of RSA,
if (bdCompare(m1, m2) < 0)
bdAdd(m1, m1, p);
bdSubtract(m1, m1, m2);
/* Let h = qInv ( m_1 - m_2 ) mod p. */
bdModMult(h, qInv, m1, p);
A very simple example of RSA encryption
This is an extremely simple example using numbers you can work out on a pocket calculator (those of you over the age of 35 can probably even do it by hand).
Select primes p=11, q=3.
n = pq = 11.3 = 33
phi = (p-1)(q-1) = 10.2 = 20
Choose e=3
Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1),
and check gcd(e, q-1) = gcd(3, 2) = 1
therefore gcd(e, phi) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1
Compute d such that ed ≡ 1 (mod phi)
i.e. compute d = e-1 mod phi = 3-1 mod 20
i.e. find a value for d such that phi divides (ed-1)
i.e. find d such that 20 divides 3d-1.
Simple testing (d = 1, 2, ...) gives d = 7
Check: ed-1 = 3.7 - 1 = 20, which is divisible by phi.
Public key = (n, e) = (33, 3)
Private key = (n, d) = (33, 7).
This is actually the smallest possible value for the modulus n for which the RSA algorithm works. Now say we want to encrypt the message m = 7,
c = me mod n = 73 mod 33 = 343 mod 33 = 13.
Hence the ciphertext c = 13.
To check decryption we compute
m' = cd mod n = 137 mod 33 = 7.
Note that we don't have to calculate the full value of 13 to the power 7 here. We can make use of the fact that
a = bc mod n = (b mod n).(c mod n) mod n
so we can break down a potentially large number into its components and combine the results of easier, smaller calculations to calculate the final value.
One way of calculating m' is as follows:-
m' = 137 mod 33 = 13(3+3+1) mod 33 = 133.133.13 mod 33
= (133 mod 33).(133 mod 33).(13 mod 33) mod 33
= (2197 mod 33).(2197 mod 33).(13 mod 33) mod 33
= 19.19.13 mod 33 = 4693 mod 33
= 7.
Now if we calculate the ciphertext c for all the possible values of m (0 to 32), we get
m 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
c 0 1 8 27 31 26 18 13 17 3 10 11 12 19 5 9 4
m 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
c 29 24 28 14 21 22 23 30 16 20 15 7 2 6 25 32
Note that all 33 values of m (0 to 32) map to a unique code c in the same range in a sort of random manner. In this case we have nine values of m that map to the same value of c - these are known as unconcealed messages. m = 0, 1 and n-1 will always do this for any n, no matter how large. But in practice, higher values shouldn't be a problem when we use large values for n in the order of several hundred bits.
If we wanted to use this system to keep secrets, we could let A=2, B=3, ..., Z=27. (We specifically avoid 0 and 1 here for the reason given above). Thus the plaintext message "HELLOWORLD" would be represented by the set of integers m1, m2, ...
(9,6,13,13,16,24,16,19,13,5)
Using our table above, we obtain ciphertext integers c1, c2, ... (3,18,19,19,4,30,4,28,19,26)
Note that this example is no more secure than using a simple Caesar substitution cipher, but it serves to illustrate a simple example of the mechanics of RSA encryption. Remember that calculating me mod n is easy, but calculating the inverse c-e mod n is very difficult, well, for large n's anyway. However, if we can factor n into its prime factors p and q, the solution becomes easy again, even for large n's. Obviously, if we can get hold of the secret exponent d, the solution is easy, too.
A slightly less simple example of the RSA algorithm
This time, to make life slightly less easy for those who can crack simple Caesar substitution codes, we will group the characters into blocks of three and compute a message representative integer for each block. ATTACKxATxSEVEN = ATT ACK XAT XSE VEN
In the same way that a decimal number can be represented as the sum of powers of ten, e.g.
135 = 1 x 102 + 3 x 101 + 5,
we could represent our blocks of three characters in base 26 using A=0, B=1, C=2, ..., Z=25 ATT = 0 x 262 + 19 x 261 + 19 = 513
ACK = 0 x 262 + 2 x 261 + 10 = 62
XAT = 23 x 262 + 0 x 261 + 19 = 15567
XSE = 23 x 262 + 18 x 261 + 4 = 16020
VEN = 21 x 262 + 4 x 261 + 13 = 14313
For this example, to keep things simple, we'll not worry about numbers and punctuation characters, or what happens with groups AAA or AAB.
In this system of encoding, the maximum value of a group (ZZZ) would be 263-1 = 17575, so we require a modulus n greater than this value.
We "generate" primes p=137 and q=131 (we cheat by looking for suitable primes around √n)
n = pq = 137.131 = 17947
phi = (p-1)(q-1) = 136.130 = 17680
Select e = 3
check gcd(e, p-1) = gcd(3, 136) = 1, OK and
check gcd(e, q-1) = gcd(3, 130) = 1, OK.
Compute d = e-1 mod phi = 3-1 mod 17680 = 11787.
Hence public key, (n, e) = (17947, 3) and private key (n, d) = (17947, 11787).
Question: Why couldn't we use e=17 here?
To encrypt the first integer that represents "ATT", we have
c = me mod n = 5133 mod 17947 = 8363.
We can verify that our private key is valid by decrypting
m' = cd mod n = 836311787 mod 17947 = 513.
Overall, our plaintext is represented by the set of integers m
(513, 62, 15567, 16020, 14313)
We compute corresponding ciphertext integers c = me mod n, (which is still possible by using a calculator)
(8363, 5017, 11884, 9546, 13366)
You are welcome to compute the inverse of these ciphertext integers using m = cd mod n to verify that the RSA algorithm still holds. However, this is now outside the realms of hand calculations unless you are very patient.
A real example
In practice, we don't have a series of small integers to encrypt like we had in the above examples, we just have one big one. We put our message into an octet string, most significant byte first, and then convert to a large integer. Also, rather than trying to represent the plaintext as an integer directly, we generate a random session key and use that to encrypt the plaintext with a conventional, much faster symmetrical algorithm like Triple DES or AES-128. We then use the much slower public key encryption algorithm to encrypt just the session key.
The sender A then transmits a message to the recipient B in a format something like this:
Session key encrypted with RSA = xxxx
Plaintext encrypted with session key = xxxxxxxxxxxxxxxxx
The recipient B would extract the encrypted session key and use his private key (n,d) to decrypt it. He would then use this session key with a conventional symmetrical decryption algorithm to decrypt the actual message. Typically the transmission would include in plaintext details of the encryption algorithms used, padding and encoding methods, initialisation vectors and other details required by the recipient. The only secret required to be kept, as always, should be the private key.
If Mallory intercepts the transmission, he can either try and crack the conventionally-encrypted plaintext directly, or he can try and decrypt the encryped session key and then use that in turn. Obviously, this system is as strong as its weakest link.
When signing, it is usual to use RSA to sign the message digest of the message rather than the message itself. A one-way hash function like SHA-1 or SHA-256 is used. The sender A then sends the signed message to B in a format like this:
Hash algorithm = hh
Message content = xxxxxxxxx...xxx
Signature = digest signed with RSA = xxxx
The recipient will decrypt the signature to extract the signed message digest, m; independently compute the message digest, m', of the actual message content; and check that m and m' are equal. Putting the message digest algorithm at the beginning of the message enables the recipient to compute the message digest on the fly while reading the message.
PKCS#1 Schemes
Algorithm: Encryption using PKCS#1v1.5 INPUT: Recipient's RSA public key, (n, e) of length k = |n| bytes; data D (typically a session key) of length |D| bytes with |D|<=k-11.
OUTPUT: Encrypted data block of length k bytes
Form the k-byte encoded message block, EB, EB = 00 || 02 || PS || 00 || D
where || denotes concatenation and PS is a string of k-|D|-3 non-zero randomly-generated bytes (i.e. at least eight random bytes).
Convert the byte string, EB, to an integer, m, most significant byte first, m = StringToInteger(EB, k)
Encrypt with the RSA algorithm c = m^e mod n
Convert the resulting ciphertext, c, to a k-byte output block, OB OB = IntegerToString(m, k)
Output OB.
The conversions in steps (2) and (4) from byte string to large integer representative and back again may not be immediately obvious. Large integers and byte (bit) strings are conceptually different even though they may both be stored as arrays of bytes in your computer.
Worked Example
Bob's 1024-bit RSA encryption key in hex format:
n=
A9E167983F39D55FF2A093415EA6798985C8355D9A915BFB1D01DA197026170F
BDA522D035856D7A986614415CCFB7B7083B09C991B81969376DF9651E7BD9A9
3324A37F3BBBAF460186363432CB07035952FC858B3104B8CC18081448E64F1C
FB5D60C4E05C1F53D37F53D86901F105F87A70D1BE83C65F38CF1C2CAA6AA7EB
e=010001
d=
67CD484C9A0D8F98C21B65FF22839C6DF0A6061DBCEDA7038894F21C6B0F8B35
DE0E827830CBE7BA6A56AD77C6EB517970790AA0F4FE45E0A9B2F419DA8798D6
308474E4FC596CC1C677DCA991D07C30A0A2C5085E217143FC0D073DF0FA6D14
9E4E63F01758791C4B981C3D3DB01BDFFA253BA3C02C9805F61009D887DB0319
A randomly-generated one-off session key for AES-128 might be D=4E636AF98E40F3ADCFCCB698F4E80B9F
The encoded message block, EB, after encoding but before encryption, with random padding bytes shown in green, 0002257F48FD1F1793B7E5E02306F2D3228F5C95ADF5F31566729F132AA12009
E3FC9B2B475CD6944EF191E3F59545E671E474B555799FE3756099F044964038
B16B2148E9A2F9C6F44BB5C52E3C6C8061CF694145FAFDB24402AD1819EACEDF
4A36C6E4D2CD8FC1D62E5A1268F496004E636AF98E40F3ADCFCCB698F4E80B9F
After RSA encryption, the output is 3D2AB25B1EB667A40F504CC4D778EC399A899C8790EDECEF062CD739492C9CE5
8B92B9ECF32AF4AAC7A61EAEC346449891F49A722378E008EFF0B0A8DBC6E621
EDC90CEC64CF34C640F5B36C48EE9322808AF8F4A0212B28715C76F3CB99AC7E
609787ADCE055839829E0142C44B676D218111FFE69F9D41424E177CBA3A435B
Note that the output for encryption will be different each time (or should be!) because of the random padding used.
Encrypting a message
For a plaintext message, say, PT="Hello world!"
that is, the 12 bytes in hex format, PT=48656C6C6F20776F726C6421
Then, using the 128-bit session key from above, KY=4E636AF98E40F3ADCFCCB698F4E80B9F
and the uniquely-generated 128-bit initialization vector (IV) IV=5732164B3ABB6C4969ABA381C1CA75BA
the ciphertext using AES-128 in CBC mode with PKCS padding is, CT=67290EF00818827C777929A56BC3305B
The sender would then send a transmission to the recipient (in this case, Bob) including the following information in some agreed format:
Recipient: Bob
Key Encryption Algorithm: rsaEncryption
Encrypted Key:
3D2AB25B1EB667A40F504CC4D778EC399A899C8790EDECEF062CD739492C9CE5
8B92B9ECF32AF4AAC7A61EAEC346449891F49A722378E008EFF0B0A8DBC6E621
EDC90CEC64CF34C640F5B36C48EE9322808AF8F4A0212B28715C76F3CB99AC7E
609787ADCE055839829E0142C44B676D218111FFE69F9D41424E177CBA3A435B
Content Encryption Algorithm: aes128-cbc
IV: 5732164B3ABB6C4969ABA381C1CA75BA
Encrypted Content:
67290EF00818827C777929A56BC3305B
The usual formats used for such a message are either a CMS enveloped-data object or XML, but the above summary includes all the necessary info (well, perhaps "Bob" might be defined a bit more accurately). CMS enveloped-data objects (yes, that's enveloped not encrypted) use ASN.1 and are encoded using either DER- or BER-encoding. Cryptographic Message Syntax (CMS) is a less-ambiguous version of the earlier PKCS#7 standard (also of the same name) and is designed to be used in S/MIME messages. The terminology for CMS and ASN.1 may sound messy, but the end results are well-defined and universally-accepted. On the other hand, the XML cryptographic standards are, to be honest, a complete mess. Pretty Good Privacy (PGP) also has a format for RSA messages, although PGP stopped using RSA because of patent issues back in the 1990s.
Nothing, of course, stops you and your recipient from agreeing on your own format and using that. But be careful, even the experts get these things wrong and accidentally give away more than they realise.
Signing using PKCS#1v1.5
Algorithm: Signing using PKCS#1v1.5 INPUT: Sender's RSA private key, (n, d) of length k = |n| bytes; message, M, to be signed; message digest algorithm, Hash.
OUTPUT: Signed data block of length k bytes
Compute the message digest H of the message, H = Hash(M)
Form the byte string, T, from the message digest, H, according to the message digest algorithm, Hash, as follows
Hash T
MD5 30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 05 05 00 04 10 || H
SHA-1 30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H SHA-25630 31 30 0d 06 09 60 86 48 01 65 03 04 02 0105 00 04 20 || H
SHA-384 30 41 30 0d 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30 || H SHA-51230 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 || H
where T is an ASN.1 value of type DigestInfo encoded using the Distinguished Encoding Rules (DER).
Form the k-byte encoded message block, EB, EB = 00 || 01 || PS || 00 || T
where || denotes concatenation and PS is a string of bytes all of value 0xFF of such length so that |EB|=k.
Convert the byte string, EB, to an integer m, most significant byte first, m = StringToInteger(EB, k)
Sign with the RSA algorithm s = m^d mod n
Convert the resulting signature value, s, to a k-byte output block, OB OB = IntegerToString(s, k)
Output OB.
Worked Example
Alice's 1024-bit RSA signing key in hex format:
n=
E08973398DD8F5F5E88776397F4EB005BB5383DE0FB7ABDC7DC775290D052E6D
12DFA68626D4D26FAA5829FC97ECFA82510F3080BEB1509E4644F12CBBD832CF
C6686F07D9B060ACBEEE34096A13F5F7050593DF5EBA3556D961FF197FC981E6
F86CEA874070EFAC6D2C749F2DFA553AB9997702A648528C4EF357385774575F
e=010001
d=
00A403C327477634346CA686B57949014B2E8AD2C862B2C7D748096A8B91F736
F275D6E8CD15906027314735644D95CD6763CEB49F56AC2F376E1CEE0EBF282D
F439906F34D86E085BD5656AD841F313D72D395EFE33CBFF29E4030B3D05A28F
B7F18EA27637B07957D32F2BDE8706227D04665EC91BAF8B1AC3EC9144AB7F21
The message to be signed is, of course, M="abc"
that is, the 3 bytes in hex format, PT=616263
The message digest algorithm is SHA-1, so H = Hash("abc") = A9993E364706816ABA3E25717850C26C9CD0D89D
The DigestInfo value for SHA-1 is T=
3021300906052B0E03021A05000414A9993E364706816ABA3E25717850C26C9C
D0D89D
The encoded message block, EB, after encoding but before signing is 0001FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00302130
0906052B0E03021A05000414A9993E364706816ABA3E25717850C26C9CD0D89D
After RSA signing, the output is 60AD5A78FB4A4030EC542C8974CD15F55384E836554CEDD9A322D5F4135C6267
A9D20970C54E6651070B0144D43844C899320DD8FA7819F7EBC6A7715287332E
C8675C136183B3F8A1F81EF969418267130A756FDBB2C71D9A667446E34E0EAD
9CF31BFB66F816F319D0B7E430A5F2891553986E003720261C7E9022C0D9F11F
Weaknesses in RSA
Small encryption exponent If you use a small exponent like e=3 and send the same message to different recipients and just use the RSA algorithm without adding random padding to the message, then an eavedropper could recover the plaintext. Using the same key for encryption and signingGiven that the underlying mathematics is the same for encryption and signing, only in reverse, if an attacker can convince a key holder to sign an unformatted encrypted message using the same key then she gets the original. Acting as an oracleThere are techniques to recover the plaintext if a user just blindly returns the RSA transformation of the input. So don't do that. Solutions
Don't use the same RSA key for encryption and signing.
If using PKCS#v1.5 encoding, use e=0x10001 for your public exponent.
Always format your input before encrypting or signing.
Always add fresh random padding - at least 8 bytes - to your message before encrypting.
When decrypting, check the format of the decrypted block. If it is not as expected, return an error, not the decrypted string.
Similarly, when verifying a signature, if there is any error whatsoever, just respond with "Invalid Signature".
More Advanced Schemes
The underlying RSA computations
c = me mod n, m' = cd mod n; s = md mod n, m' = se mod n
are always the same, but there are many variants of how these can be used inside an encryption or digital signature scheme. Here are some of them.
RSAES-OAEP
The OAEP encoding technique for encryption is described in PKCS#1 version 2 and in IEEE P136. It is more secure than the PKCS#1v1.5 encoding method described above, perhaps provably secure. The encoding technique involves a mask generation function (MGF) based on a hash function and there is no obvious structure in the encoded block, unlike the PKCS#1v1.5 encoding method. Despite being the recommended method for the last decade, it is not used in practice as much as you'd expect. RSASSA-PSS
The PSS encoding method is used to encode before creating a signature. The technique is described in PKCS#1v2.1 and is similar in design to the OAEP encoding used for encryption involving an MGF based on a hash function. However, there are active patents associated with this method, so sensible implementators avoid it like the plague. There are also currently no known weaknesses with the PKCS#1v1.5 signature scheme.
X9.31 Signature Scheme
It requires using strong primes derived in a way to avoid particular attacks that are probably no longer relevant. X9.31 uses a method of encoding the message digest specific to the hash algorithm. It expects a key with length an exact multiple of 256 bits.he scheme allows for the public exponent to be an even value, but we do not consider that case here; all our values of e are assumed to be odd. The message digest hash, H, is encapsulated to form a byte string as follows EB = 06 || PS || 0xBA || H || 0x33 || 0xCC
where PS is a string of bytes all of value 0xBB of length such that |EB|=|n|, and 0x33 is the ISO/IEC 10118 part number for SHA-1. The byte string, EB, is converted to an integer value, the message representative, f. Algorithm: Forming an X9.31/RSA2 signature value from the message representative (for odd e). INPUT: Signer's RSA private key, (n, d); integer, f, where 0 <= f < n and f ≡ 12 (mod 16).
OUTPUT: Signature, an integer s, 0 <= s < n/2, i.e. a value at least one bit shorter than n.
t = fd mod n
s = min{t, n-t}
Output s.
The integer, s, is converted to a byte string of length |n| bytes. Algorithm: Extracting the message representative from an X9.31/RSA2 signature value (for odd e). INPUT: Signer's RSA public key, (n, e); signature, s.
OUTPUT: Message representative, f, such that t ≡ 12 (mod 16), or "invalid signature".
If s is not in [0,(n-1)/2], output "invalid signature" and stop.
Compute t = se mod n
If t ≡ 12 (mod 16) then let f = t.
Else let f = n-t. If NOT f ≡ 12 (mod 16), output "invalid signature" and stop.
Output f.
The integer f is converted to a byte string of length |n| bytes and then parsed to confirm that all bytes match the required format EB = 06 || PS || 0xBA || H || 0x33 || 0xCC
If not, output "invalid signature" and stop; otherwise output the extracted message digest hash, H. ISO/IEC 9796
IOS/IEC 9796 is an old standard devised before there was a recognised message digest function like MD5 or SHA-1. It allows the entire message to be recovered. Unfortunately, it is considered broken for signing plain text messages, but is still OK for signing message digest values.
The encapsulation mechanism weaves the input bytes into a format exactly one bit shorter than the RSA key. The signing mechanism is similar to that in ANSI X9.31 described above, but the message representative, f, is required to be f ≡ 6 (mod 16), instead of modulo 12. In other words, make sure the last 4 bits are equal to 0x6 instead of 0xC.
RSA-KEM
The RSA-KEM Key Transport Algorithm encrypts a random integer with the recipient's public key, and then uses a symmetric key-wrapping scheme to encrypt the keying data. KEM stands for Key Encapsulation Mechanism. The general algorithm is as follows
Generate a random integer z between 0 and n-1.
Encrypt the integer z with the recipient's RSA public key: c = ze mod n.
Derive a key-encrypting key KEK from the integer z.
Wrap the keying data using KEK to obtain wrapped keying data WK.
Output c and WK as the encrypted keying data.
This method has a higher security assurance than PKCS#1v1.5 because the input to the underlying RSA operation is random and independent of the message, and the key-encrypting key KEK is derived from it in a strong way.
Algorithm: Ferguson-Schneier Encrypt Random Key with RSA. INPUT: Recipient's RSA public key, (n, e).
OUTPUT: Content encryption key, CEK; RSA-encrypted CEK, c.
Compute the exact bit length of the RSA key, k = ceiling(log2(n+1)).
Choose a random r in the interval [0, 2k-1].
Compute the content encryption key by hashing r, CEK=Hash(r).
c = re mod n.
Output CEK and c.
For a plaintext message, m, the transmission sent to the recipient is IntegerToString(c) || ECEK(m), where ECEK(m) is the result of encrypting m with a symmetrical encryption algorithm using key, CEK. Given that the recipient knows the size of the RSA key and hence the exact number of bytes needed to encode c, it is a simple matter to parse the input received from the sender.
Notation and Conventions
We use the following notation and conventions in this page.
A || B denotes concatenation of byte (or bit) strings A and B.
|B| denotes the length of the byte (or bit) string B in bytes.
|n| denotes the length of the non-negative integer n in bytes, |n| = ceiling(log256(n+1)).
IntegerToString(i, n) is an n-byte encoding of the integer i with the most significant byte first (i.e. in "big-endian" order). So, for example, IntegerToString(1, 4)=00000001,
IntegerToString(7658, 3)=001DEA
StringToInteger(S, n) is the integer represented by the byte string S of length n bytes with the most significant byte first.
ceiling(x) is the smallest integer, n, such that n ≥ x.
to be continued...
PKE: The RSA Algorithm
The RSA algorithm, named for its creators Ron Rivest, Adi Shamir, and Leonard Adleman (RSA) is currently one of the favorite public key encryption methods. Here is the algorithm:
Choose two (in practice, large 100 digit) prime numbers p and q and let n = pq.
Let Pi be the block of (plain) text to be encrypted. Actually Pi is the numerical equivalent of the text which may either be single letters or blocks of letters, just as long as http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img325.gif.
Choose a random value E (usually small) such that E is relatively prime to http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img327.gif. Then the encrypted text is calculated from http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img329.gif
The pair of values (n,E) act as the public key.
To decode the ciphertext, we need to find an exponent D, which is known only to the person decoding the message, such that http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img333.gif
Note that http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img335.gif. Then we may calculate
http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img337.gif
This step is based on the following result:
http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img339.gif
where http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img341.gif Show that this result is true.
By Euler's theorem
http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img343.gif
provided E and http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img327.gif are relatively prime, which is true by the choice of E. So we obtain
http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img351.gif
http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img353.gif
http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img355.gif
Therefore, we have an equation that can be used to find the "key" exponent D. The central result of the RSA algorithm is that this equation is computationally solvable in polynomial time (actually using the Euclidean Algorithm) whereas solving by factoring n requires exponential computational time.
P.S.Since http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img349.gif, then http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img350.gif for some integer m. Thus, applying Euler's theorem we have http://www2.krellinst.org/UCES/archive/modules/charlie/pke/img352.gif
I think I'm not making ya' troubleunderstood... :D
Powered by vBulletin® Version 4.2.5 Copyright © 2024 vBulletin Solutions Inc. All rights reserved.