Understanding-dictionary About Encryption Systems !
Hello to all !
Because the questions about this subject has added,
i decided to write a little tutorial about how the basic encryption system functionallity are !
I hope i can help some of you for the basic understanding with this topic.
Success
TRINITY
CONAX
Conax uses same basic principles to encrypt channels as do other encryption systems.
Basically speaking a encrypted "Control Word" or ECW for short is sent to every card in a message called an Entitlement Control Message or ECM.
A new ECW is sent to every card simultaneously every 5 or 10 seconds or so.
The Card uses the current Operational Key (Key 20, Key21) to decode this ECW into a decoded Control Word or DCW.
The algorithm used to do this decoding of the ECW into DCW is called RSA (a little more about how this works later)
The DCW is then returned by the Smart Card to the CAM, where it is used to decode the incoming video signal. This is done within the CAM using a system called CSA (Common Scrambling Algorithm) to decode the incoming video into a veiwable picture.
From the above we can understand that all cards have the same Operational Key values, because they all have to decode the same ECW to clear a channel. Got that? Good....
Now where do those Operational keys come from and how do they get into the card. Well in the old days they would be preloaded into all the cards when they were manufactured. The problem with this (for the providers, not for us!) is that when hackers opened any one card and got the keys, the only way the provider could stop pirate veiwing would be to replace all the cards. Expensive to do!
So with current systems (like Conax) we have a further step up the ladder.
The Operational keys are sent to all the subscriber cards over the air in a message called an EMM (Entitlement Management Message).
This EMM contains the new Operation Keys to be used next.
Obviously hackers are not allowed to log these new Operation Keys being sent, so again these operational keys in the EMM are encrypted using RSA.
However there is an important difference between EMM and ECM. Where ECM are sent simultaneously to all cards, EMM are sent separately to every card in turn.
An EMM contains an Address of a specific card (known as UA or SA), and an encrypted operational key. The operational key is encrypted in RSA using a Master Key.
This Master Key in conax is key10, and every single card has it's own unique Master Key 10, so a card can only decrypt the EMM addressed specifically to that card.
In other words every EMM contains different encrypted data that can only be decoded by the card it is meant for.
This means that Conax can choose which cards it want's to update with the new key 20 or 21, and which cards it no longer wants to update - like when the subscription expires for example, or a card is reported stolen or lost.
The idea behind all this is that if hackers extract the MK10 from a card, and then publish that key and UA, all Conax needs to do is find the compromised key and address, then stop updating that card and all peoples copies that use the same key.
This is the reason why Master Keys are kept secret amongst small groups of hackers.
What was not considered at the time these systems were invented, is tha tpeople would have such a thing as the internet, where the current Operational keys can be published to many people very quickly, even if the change every day or more often (anyone remember good ol' sexview - 3 updates per day! )
Now a little about RSA itself
This is how it works:
* Find 2 very large primes, p and q.
* Find n=pq (the public modulous).
* Choose e, such that e<n and relatively prime to (p-1)(q-1).
* Compute d=e^-1 mod[(p1-)(q-1)] OR ed=1[mod (p-1)(q-1)].
* e is the public exponent and d is the private one.
* The public-key is (n,e), and the private key is (n,d).
* p and q should never be revealed, preferably destroyed
Encryption is done by dividing the target message into blocks smaller than n and by doing modular exponentiation:
c=m^e mod n
Decryption is simply the inverse operation:
m=c^d mod n
RSA, the first full fledged public key cryptosystem was designed by Rivest, Shamir, and Adleman in 1977.
RSA gets its security from the apparent difficulty in factoring very large composites.
However, nothing has been proven with RSA. It is not proved that factoring the public modulous is the only (best) way to break RSA.
There may be an as yet undiscovered way to break it. It is also not proven that factoring has to be as hard as it is. There exists the possiblity that an advance in number theory may lead to the discovery of a polynomial time factoring algorithm.
But, none of these things has happened, and no current research points in that direction.
However, 3 things that are happening and will continue to happen that take away from the security of RSA are: the advances in factoring technique, computing power and the decrease in the cost of computing hardware.
These things, especially the first one, work against the security of RSA.
However, as computing power increases, so does the ability to generate larger keys.
It is much easier to multiply very large primes than it is to factor the resulting composite (given today's understanding of number theory).
I hope that gives an insight into how these things work. If any of the above doesn't make sense, ask and I will clarify what I can
If you want to study further search the net for links regarding.
RSA
Prime Numbers
Cryptology
Crytanalysis
RSA Attacks
Brute Force Attacks
Timing Attacks
Or just ask here for more info, I'm sure others as well as myself can help you in your studies
Report this post to a moderator | IP: Logged
05-06-2003 07:17 PM
OK let's see if I can explain this a bit more clear than my ramblings above as maybe some did not follow it
To answer direct the questions asked by Hide who started this thread
Quote Hide
--------------------------------------------
Are there cards inside ready own Mkeys and Opkeys?
And it´s returning data too crypted by RSA or what? (CAM---rsa-->CARD----->CAM)
--------------------------------------------
Right lets see. There are TWO distinct processes going on in Conax (and just about all other encryptions)
1. Process for Decoding the actual picture/sound
-----------------------------------------------
For this the Conax card contains Operational Keys Key20 and 21, but only one of these is used at a time(see below for more about this) - marked (*)
The Process is:
a. CAM sends Encrypted CW to CARD in a message called an ECM
b. CARD uses key 20 or 21 to decode Encrypted CW into Decrypted CW (which is done using the RSA algorithm)
c. Decrypted CW is returned from CARD to CAM
d. CAM uses decrypted CW to decode the video
This process repeats every few seconds when a new ECW is sent to be decoded by the card. Every new ECW (encrypted Control WOrd) arrives in an ECM (Entitlement Control Message) All cards receive the SAME ECM at the SAME time.
If you have a valid key 20 or 21 then you can watch Conax until the key20 or 21 changes - once every day, week, month, whatever they decide it will last for.
2. Process for updating the Operational Keys Key20/21
---------------------------------------------------------------------
a. CAM sends new Encrypted Key 20 or 21 to CARD in a message called an EMM.
b. CARD decrypts the key 20 or 21 using its own UNIQUE master key 10 (to ensure the card decodes the correct EMM they attach a unique address to each EMM so the card knows which EMM to decrypt)
c. The decrypted key 20 or 21 is NOT sent back to the cam. It STAYS IN THE CARD for use in the above process 1.
Every EMM is unique to the card it was meant for.
Every EMM has a different encoded key 20 or 21, EVERY CARD HAS A UNIQUE KEY 10
However when the EMM is decoded with the correct key 10, every card produces the SAME decoded key20 or 21
Like this:
Encrypted Key 20 123456789 + MK10 (card a) = key 20 12AB4356
Encrypted Key 20 342575357 + MK10 (card b) = Key 20 12AB4356
Encrypted Key 20 12AB4EC21 + MK10 (card c) = Key 20 12AB4356
If you have a valid Master Key (Key10) and UA (Unique Address) then you can make an auto update file which will update the new key 20 or 21 when it is sent.
Now does THAT make more sense?? If not I'm happy to go through this and clarify things as long as you folks have a wish to understand more about what this hobby is really about.
Oh couple other things to mention (otherwise others here will tell me the above is wrong)
First thing.
In reality as many providers have millions of subscribers, they don't have time to send new operqational keys to every single card, one by one, using the UA (Unique Address)
So what they do in reality is update whole groups of cards at the same time (say 4096 cards per group) using the SA (Shared Address). If you understood post above you will realise that all cards from the same SA must have the same MK10!
Second thing (*)
There is some rumours/talk that since Conax changed cards in some SA groups, they have modified thier system to use BOTH key 20/21 to process the ECW. I have seen no evidence that this is true, but rumours persist.
SECA (PART 1)
(It works for seca1 but also similar to seca2)
This document is a first attempt at describing the digital Pay-TV encryption
system Mediaguard as sold by SECA (Societe Europeene de Controle D'Acces) and
used by some European broadcasters including CANAL+. It's not complete but it
explains the basic concepts and the most important instructions including the
decryption algorithm used and the message signature calculation. More will be
added as other functionality becomes clear.
I have written it for educational purposes only and have kept the description
at a theoretical level so that it is instructive for the reader to compare
and contrast the Mediaguard system with Eurocrypt. In some ways is it very
similar to Eurocrypt in that some concepts remain (eg Issuer, Unique Address,
Shared Address) but in others it is very different (eg Superencryption,
Pay-per-View). As far as I can tell this is the first time that different
systems have been studied to understand the requirements of a modern Pay-TV
encryption system in general. It is not my intention that the information
contained herein is used to break the laws of any country; no key information
is included, nor are any details of how to build working smartcards. It
assumes that the reader is familiar with the Eurocrypt system and uses terms
defined in that system where appropriate without explanation.
The reader should be grateful to Amadeus who has been responsible for much of
the work and to MacDouf who wrote some introductory material originally.
COMMAND STRUCTURE and ANSWER-TO-RESET
The Mediaguard system complies with the ISO 7816 standard for packet structure
and protocol, using 5 byte command headers of the form
CLA, INS, P1, P2, P3.
The only valid instruction class is C1 unlike Eurocrypt which supports both
87 and CA.
The ATR string is typically
3B F7 11 00 01 40 xx xx xx 03 0E 6C B6 D6 90 00
which tells us that the Direct Convention is used (least significant bit
first) at a transmission speed of 9600 baud, unlike Eurocrypt which uses the
Inverse Convention. The 3 masked bytes can vary, but not with each individual
card.
STARTUP
Immediately after the ATR is received the CAM sends the command header
C1 34 00 00 03
to the card which is a request for information. The card responds with 34
(the normal ISO7816 protocol) and receives 3 bytes from the CAM. These bytes
tell the card what information the CAM requires, and at startup they are
always 04 00 01. We'll look at other information requests later.
The CAM then issues
C1 32 00 00 0D
which is a request to send the information. In Mediaguard the C1 34/C1 32
commands act in pairs, the first defining the information and the second
requesting it.
The card responds with
32 B2 <11 data bytes> 04 90 00.
The data bytes can vary but are typically 01 00 00 00 00 00 00 00 00 FF FF.
The dialogue is analagous to the class 87 processing in Eurocrypt, and indeed,
it's possible for the broadcaster to send a command which disables the
startup string in the same way that the FAC block can be disabled in
Eurocrypt thus preventing the card from starting up.
CARD IDENTIFICATION
Each card has a 9-digit number printed on it which, when converted to
hexadecimal gives the 4-byte Unique Address (UA) of the card. Immediately
after the startup sequence the CAM issues
C1 0E 00 00 08
which asks the card to identify itself. The card responds with
0E 00 25 00 00 <UA> 90 00.
I don't know the significance of the first 4 bytes and I have seen other
values for the second byte; maybe its a region code.
Incidentally, facilities exist whereby the broadcaster can update a card's
UA so there should be no need to send out new cards when official cards get
hacked, this can be done over-the-air.
ENTITIES SUPPORTED
As with some Eurocrypt decoders the Mediaguard CAM wants to know at an early
stage how many and which entities are supported by the card. It begins the
process by issuing
C1 16 00 00 07.
The card responds with
16 00 00 <Entity Bitmap> <2 bytes> FF 90 00.
The Entity Bitmap consists of 2 bytes and each bit represents one entity. If
a bit is set the corresponding entity is supported. Entities are numbered from
0 from right to left. So if the Entity Bitmap is 0x03FF entities 0-9 are
supported and entities 11-15 aren't.
The two bytes following the Entity bitmap are usually 0x0000 but represent
various permissions which the card has. A typical C1 16 string is
00 00 0F FF 00 00 FF indicating that 12 entities are supported.
Entity 0 is the card Issuer Entity and entities 1-15 are Programme Provider
Entities such as CANAL+ and CanalSatellite.
Having identified the number of entities supported the CAM now proceeds to
identify them by sending
C1 12 00 00 18.
and the card responds with
12
00 00
53 45 43 41 20 20 20 20 20 20 20 20 20 20 20 20
00 00 00 00 00 00
90 00.
The first two bytes (0x0000) are the Entity Identifier, followed by 16 bytes
of the entity name ('SECA' in ASCII), followed by zeros. The issuer entity is
thus Seca with an ID of 0000. The value of parameter P1 in the C1 12 command
specifies the entity to be displayed.
The CAM then asks for the same information for each of the provider entities
beginning with
C1 12 01 00 18
and could receive
12
00 1C
28 49 29 4d 65 64 69 61 73 65 74 20 20 20 20 20
<UA>
29 9F
90 00.
The provider in this case is (I)Mediaset with an ID of 001C. Note that after
the provider name the card's UA is displayed followed by the subscription
expiry date. By the way, dates are coded exactly the same as in Eurocrypt M
but from a base year of 1990.
SUBSCRIPTIONS SUPPORTED
The last stage in the introductory process is where the CAM identifies which
Packages the card supports for each provider. A Package is a subset of the
total programmes supplied by a provider, but marketed as a single unit. For
example you could subscribe to some film channels, some sport and a nature
channel and pay incremented subscriptions based on your choice. That would
entitle you to view some packages, but not all (eg music). Each provider can
define and market up to 64 packages.
To ascertain the packages subscribed the CAM issues
C1 34 00 00 03
and, as before the card responds '34' to receive 00 00 00.
The CAM then sends
C1 32 P1 00 20
where P1 represents the entity ID.
The card responds with (for example)
32
83 00 00 00 00 00 00 00 07
04 FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF
FF FF FF FF FF FF 90 00.
The card sends '83' followed by the Package Bitmap, then '04' to indicate the
end of the data. The rest is just padding.
The Package Bitmap is similar to the Provider Bitmap; packages are numbered
from 0 from right to left and a set bit indicates that package number is
active. So in the example, packages 0,1 and 2 are active. Note that package
numbers run from 0x00 to 0x3F.
The CAM repeats the C1 34/C1 32 cycle for each entity in the card and has then
completed the long and rather tedious opening sequence.
We can now look at how programme decryption occurs.
SECA (PART 2)
ENTITLEMENT CONTROL
Mediaguard's Entitlement Control System is remarkably similar to Eurocrypt's
in that it:
- uses a pair of command headers C1 3C/C1 3A to supply
encrypted data and receive decrypted data just like the
CA 88/CA C0 Eurocrypt pair
- requires two 8-byte control words to be decrypted using
operation keys
- sends entitlement parameters in the data stream for the
card to check against its authorisations
- uses a key-dependent message signature which the card
checks to validate the message before decryption.
It does however contain some 'under the bonnet' tricks which might make it
less easy to hack than Eurocrypt, but time will tell.
Eurocrypt's ECS contains three stages:
- select entity (CA A4)
- send encrypted control words and entitlement data (CA 8
- receive decrypted control words (CA C0).
Mediaguard only needs two stages since the entity is selected by the use of
parameter P1 for the provider. Also, whereas Eurocrypt's parameters are in the
form ID, Length, Data, Mediaguard's parameter IDs are chosen so that their
length is part of the ID. The most significant nybble of a parameter ID also
determines the length of the parameter data as follows:
Parameter ID Data Length
0x0n to 0xCn 0x00 to 0x0C
0xDn 0x10
0xEn 0x18
0xFn 0x20
where n is some hex value 0-F.
So, for example, parameter 0x71 has 7 bytes of data, but parameter 0xD1 has
16 data bytes.
Every 10 seconds or so the Mediaguard CAM sends a command header like
C1 3C 09 0C 27.
The card responds '3C' and receives data like
71 00 00 19 07 CF 00 04
27 12 89
13 01
D1 FA 55 DA FE 46 B4 E0 95 62 0D 37 9F 66 59 2A 04
82 92 A9 DB E9 C2 9C F4 9D
90 00.
Parameter P1 defines the provider (entity 0x09) and P2 the key to be used for
decryption (0x0C).
Eurocrypt devotees will recognise the pattern here. The data stream consists
of parameter 0x71 (0x00 -> 0x04), parameter 0x27 (0x12 0x89), parameter 0x13
(0x01) parameter 0xD1 (0xFA -> 0x04) and parameter 0x82 (0x92 -> 0x9D). As far
as I can tell the card ignores parameter 0x71, and for many providers it's
always zero. Parameter 0x27 is the transmission date (9th April 1999) and
parameter 0x13 is the package the programme is transmitted in. Parameter 0xD1
is the two 8-byte encrypted control words and parameter 0x82 is the 8-byte
message signature, akin to the Eurocrypt CA 88 hash.
It's pretty obvious what the card does. It first checks the signature, then
tests that the transmission date is before the subscription expiry date for
the provider, then checks the package bitmap that package 0x01 bit is set. It
then decrypts the control words and returns 90 00 when all is done or 9x xx
if any test fails.
Upon receipt of the terminator 90 00 the CAM sends
C1 3A 00 00 10
asking for the two decrypted control words and the card responds with
3A xx xx xx xx xx xx xx xx
xx xx xx xx xx xx xx xx
90 00
at which point the picture and sound appear.
There are 15 parameters which can be used with C1 3C. It's possible to decrypt
a single control word (parameter 0x87). The broadcaster can transmit the
maturity rating of the programme in the data stream (0x12) and the card will
check it against the Reference Maturity Rating if set by a PIN controlled
operation (see later) to enforce parental control. Packages can be promoted to
subscribers via the 0x04 parameter which offers free viewing by bypassing the
package check. Pay-per-View programmes with or without previews can be
controlled with parameters 0x15, 0x19, 0x2C, 0x2D and 0x31. Of these the
Preview parameter 0x19 is the most interesting; the data is a counter which
is decremented every time a C1 3C command is processed and when the counter
is exhausted control word decryption stops.
All of the foregoing raises the question of the algorithms used for control
word decryption and message signature, so let's examine them.
DECRYPTION ALGORITHM
The Mediaguard decryption algorithm operates on an 8-byte crypted word using
a 16-byte key to produce an 8-byte plain word. The 16-byte key consists of an
8-byte Primary key and an 8-byte Secondary key. Sometimes the Secondary key is
the same as the Primary key, at other times it is different. In order to
clarify this confusing situation let's look at keys in more detail.
Both Primary and Secondary keys are numbered from 0x00 to 0x0F so there are
potentially 16 of each. It looks like the operation keys are 0x0C to 0x0F and
that keys 0x00 to 0x0B are management keys. But Primary keys can, at the
broadcaster's whim, be numbered as 0x10 to 0x1F when they are stored in the
card. Only Primary keys so numbered can be used with the equivalent Secondary
key. The P1 parameter of the C1 32 command determines whether this will
happen, if it is of the form 0x1n.
Here's some examples:
C1 32 04 0E P3 Use Primary key 0x0E, 0x0E from provider 0x04
C1 32 14 0E P3 Use Primary key 0x0E, Secondary key 0x0E from
provider 0x04 if Primary key 0x0E is numbered
0x1E; if not, use Primary key 0x0E, 0x0E.
So now you should understand how the 16-byte key is formed for the algorithm.
The algorithm consists of two stages, key preparation and data manipulation.
Key Preparation
Imagine the key bytes are wrapped around like this:
...k15, k16, k1, k2, ..., k13, k14...
Start at k1, take the byte which 'precedes it' (ie k16), XOR this with the
byte which 'follows it' (ie k2) and a constant C. Use this as the index into
the first 256 byte table T1 and XOR the result with k1. This is the new value
of k1. The constant C has an initial value of 0, and table T1 is shown at the
end of the section.
So new k1 = old k1 XOR T1(k16 XOR k2 XOR C).
Follow this process 3 more times on k2-k4 to give:
new k2 = old k2 XOR T1(k1 XOR k3 XOR C)
new k3 = old k3 XOR T1(k2 XOR k4 XOR C)
new k4 = old k4 XOR T1(k3 XOR k5 XOR C).
Increment the constant C and do 4 more rounds on k5-k8 to give:
new k5 = old k5 XOR T1(k4 XOR k6 XOR C)
new k6 = old k6 XOR T1(k5 XOR k7 XOR C)
new k7 = old k7 XOR T1(k6 XOR k8 XOR C)
new k8 = old k8 XOR T1(k7 XOR k9 XOR C)
Increment C again and do 4 more rounds to get values for new k9, k10, k11,
k12. Repeat this last process to get values for new k13, k14, k15 and k16. At
this point C=3.
Increment C to 4 and start at the beginning again and do a complete round for
k1...k16, finishing with C=7.
Do two more complete rounds incrementing C and forming new values for all 16
'k' bytes. At this point C=15 and you've done 16 operations 4 times.
That is the end of the key preparation stage and the final values of
k1,...,k16 are what is used in the data manipulation stage.
SECA (PART 3)
DATA MANIPULATION
The algorithm consists of 16 rounds. Each round operates only on 4 key bytes
and 4 data bytes. If the key bytes (after the key preparation stage) are
K1,...,K16 and the data bytes are d1,...,d8:
- rounds 1,5,9,13 use key bytes K13-K16 and data bytes d5-d8
- rounds 2,6,10,14 use K9-K12 and d5-d8
- rounds 3,7,11,15 use K5-K8 and d5-d8
- rounds 4,8,12,16 use K1-K4 and d5-d8.
Each round:
- XORs the key bytes with the data bytes
- performs the core function on the data bytes to give 4 new data
values
- XORs these values with the other 4 data bytes to give the 4 data
values d5-d8 for the next round
- processes the key bytes to give new key bytes for use in a later
round.
Step One - XOR key bytes with data bytes
----------------------------------------
This is simply:
d5 = K(i) XOR d5
d6 = K(i+1) XOR d6
d7 = K(i+2) XOR d7
d8 = K(i+3) XOR d8
where i = 13 for rounds 1,5,9,13
9 for rounds 2,6,10,14
5 for rounds 3,7,11,15
1 for rounds 4,8,12,16.
Step Two - Perform the core function
------------------------------------------
First do 4 table lookups on Table 1:
d5 = T1(d5), d6 = T1(d6), d7 = T1(d7), d8 = T1(d
Then use Table 2 (see below) as follows '~' means 'swap nybbles':
d5 = d8 XOR d5
d7 = T2[(~d + d7]
d8 = d7 XOR d8
d6 = T2[(~d7) + d6]
d7 = d6 XOR d7
d5 = T2[(~d6) + d5]
Then use Table 1 as follows:
d6 = d5 XOR d6
d8 = T1[(~d5) + d8]
d5 = d8 XOR d5
d7 = T1[(~d + d7]
d8 = d7 XOR d8
d6 = T1[(~d7) + d6]
Finally do:
d7 = d6 XOR d7
d6 = d5 XOR d6.
If any of the additions result in a value larger than 0xFF, 0x0100 is
subtracted from the result before performing the table lookup.
Step Three - Get data values for the next round
-----------------------------------------------
These are obtained from Table 2 as follows:
d1 = T2(d6) XOR d1
d2 = T2(d XOR d2
d3 = T2(d5) XOR d3
d4 = T2(d7) XOR d4
Data values d1 and d5, d2 and d6, d3 and d7, d4 and d8 are then swapped ready
for the next round.
At the end of the 16th round this swap is not performed and the decrypted
data is d1,...,d8.
Step Four - Get new key bytes for a later round
-----------------------------------------------
Perform the following operations:
K(i+3) = K(i+3) XOR T1[K(i+4) XOR K(i+2) XOR C]
K(i+2) = K(i+2) XOR T1[K(i+3) XOR K(i+1) XOR C]
K(i+1) = K(i+1) XOR T1[K(i+2) XOR K(i) XOR C]
K(i) = K(i) XOR T1[K(i+1) XOR K(i-1) XOR C]
where i = 13 for rounds 1,5,9,13
9 for rounds 2,6,10,14
5 for rounds 3,7,11,15
1 for rounds 4,8,12,16.
Where the above formulas give K suffixes outside the range 1-16, the values
should be wrapped around, eg K17 = K1, K0 = K16.
C is a value based on the round number. For rounds 1,2,...,16 C has the value
0x0F,0x0E,,,0x00.
TABLES
Table 1:
02ah,0e1h,00bh,013h,03eh,06eh,032h,048h
0d3h,031h,008h,08ch,08fh,095h,0bdh,0d0h
0e4h,06dh,050h,081h,020h,030h,0bbh,075h
0f5h,0d4h,07ch,087h,02ch,04eh,0e8h,0f4h
0beh,024h,09eh,04dh,080h,037h,0d2h,05fh
0dbh,004h,07ah,03fh,014h,072h,067h,02dh
0cdh,015h,0a6h,04ch,02eh,03bh,00ch,041h
062h,0fah,0eeh,083h,01eh,0a2h,001h,00eh
07fh,059h,0c9h,0b9h,0c4h,09dh,09bh,01bh
09ch,0cah,0afh,03ch,073h,01ah,065h,0b1h
076h,084h,039h,098h,0e9h,053h,094h,0bah
01dh,029h,0cfh,0b4h,00dh,005h,07dh,0d1h
0d7h,00ah,0a0h,05ch,091h,071h,092h,088h
0abh,093h,011h,08ah,0d6h,05ah,077h,0b5h
0c3h,019h,0c1h,0c7h,08eh,0f9h,0ech,035h
04bh,0cch,0d9h,04ah,018h,023h,09fh,052h
0ddh,0e3h,0adh,07bh,047h,097h,060h,010h
043h,0efh,007h,0a5h,049h,0c6h,0b3h,055h
028h,051h,05dh,064h,066h,0fch,044h,042h
0bch,026h,009h,074h,06fh,0f7h,06bh,04fh
02fh,0f0h,0eah,0b8h,0aeh,0f3h,063h,06ah
056h,0b2h,002h,0d8h,034h,0a4h,000h,0e6h
058h,0ebh,0a3h,082h,085h,045h,0e0h,089h
07eh,0fdh,0f2h,03ah,036h,057h,0ffh,006h
069h,054h,079h,09ah,0b6h,06ch,0dch,08bh
0a7h,01fh,090h,003h,017h,01ch,0edh,0d5h
0aah,05eh,0feh,0dah,078h,0b0h,0bfh,012h
0a8h,022h,021h,03dh,0c2h,0c0h,0b7h,0a9h
0e7h,033h,0fbh,0f1h,070h,0e5h,017h,096h
0f8h,08dh,046h,0a1h,086h,0e2h,040h,038h
0f6h,068h,025h,016h,0ach,061h,027h,0cbh
05bh,0c8h,02bh,00fh,099h,0deh,0ceh,0c5h
Table 2:
0bfh,011h,06dh,0fah,026h,07fh,0f3h,0c8h
09eh,0ddh,03fh,016h,097h,0bdh,008h,080h
051h,042h,093h,049h,05bh,064h,09bh,025h
0f5h,00fh,024h,034h,044h,0b8h,0eeh,02eh
0dah,08fh,031h,0cch,0c0h,05eh,08ah,061h
0a1h,063h,0c7h,0b2h,058h,009h,04dh,046h
081h,082h,068h,04bh,0f6h,0bch,09dh,003h
0ach,091h,0e8h,03dh,094h,037h,0a0h,0bbh
0ceh,0ebh,098h,0d8h,038h,056h,0e9h,06bh
028h,0fdh,084h,0c6h,0cdh,05fh,06eh,0b6h
032h,0f7h,00eh,0f1h,0f8h,054h,0c1h,053h
0f0h,0a7h,095h,07bh,019h,021h,023h,07dh
0e1h,0a9h,075h,03eh,0d6h,0edh,08eh,06fh
0dbh,0b7h,007h,041h,005h,077h,0b4h,02dh
045h,0dfh,029h,022h,043h,089h,083h,0fch
0d5h,0a4h,088h,0d1h,0f4h,055h,04fh,078h
062h,01eh,01dh,0b9h,0e0h,02fh,001h,013h
015h,0e6h,017h,06ah,08dh,00ch,096h,07eh
086h,027h,0a6h,00dh,0b5h,073h,071h,0aah
036h,0d0h,006h,066h,0dch,0b1h,02ah,05ah
072h,0beh,03ah,0c5h,040h,065h,01bh,002h
010h,09fh,03bh,0f9h,02bh,018h,05ch,0d7h
012h,047h,0efh,01ah,087h,0d2h,0c2h,08bh
099h,09ch,0d3h,057h,0e4h,076h,067h,0cah
03ch,0fbh,090h,020h,014h,048h,0c9h,060h
0b0h,070h,04eh,0a2h,0adh,035h,0eah,0c4h
074h,0cbh,039h,0deh,0e7h,0d4h,0a3h,0a5h
004h,092h,08ch,0d9h,07ch,01ch,07ah,0a8h
052h,079h,0f2h,033h,0bah,01fh,030h,09ah
000h,050h,04ch,0ffh,0e5h,0cfh,059h,0c3h
0e3h,00ah,085h,0b3h,0aeh,0ech,00bh,0feh
0e2h,0abh,04ah,0afh,069h,06ch,02ch,05dh
SECA (PART 4)
MESSAGE SIGNATURE ALGORITHM
It looks like only one signature algorithm is used for both ECM and EMM
messages.
The procedure consists of the following steps:
- initialisation of an 8-byte hash buffer
- XORing of 8 input data bytes with the buffer contents
- execution of the signature algorithm
- repetition of the last 2 steps until all input bytes have been
processed
- comparison of the result with the 8 signature data bytes.
The signature algorithm is the reverse of the decryption algorithm (like
Eurocrypt S), so I don't need to describe it in so much detail as the
decryption algorithm.
The hash buffer is initialised based on the value of the most significant
bits 7-5 of parameter P1 as follows:
- P1(7-5) = 1: initialise to (last 6 bytes of the C1 0E 00 00 08
response),0,0
- P1(7-5) = 2: initialise to the card UA
- P1(7-5) = 3: initialise to the card SA (see below)
- P1(7-5) = any other value: initialise to zero.
The algorithm consists of 16 rounds. Each round operates only on 4 key bytes
and 4 data bytes. If the key bytes (after the key preparation stage) are
K1,...,K16 and the data bytes are d1,...,d8:
- rounds 1,5,9,13 use key bytes K1-K4 and data bytes d5-d8
- rounds 2,6,10,14 use K5-K8 and d5-d8
- rounds 3,7,11,15 use K9-K12 and d5-d8
- rounds 4,8,12,16 use K13-K16 and d5-d8.
Each round:
- processes the key bytes to give new key bytes for use in a later
round
- XORs the key bytes with the data bytes
- performs the core function on the data bytes to give 4 new data
values
- XORs these values with the other 4 data bytes to give the 4 data
values d5-d8 for the next round.
The order of operations is slightly different to the decryption order since
the process is the reverse of the decryption process. Its similar to the
'left shifts, DES function' and 'DES function, right shifts' in Eurocrypt M
and S.
Step One - Get new key bytes for a later round
-----------------------------------------------
Perform the following operations:
K(i) = K(i) XOR T1[K(i+1) XOR K(i-1) XOR C]
K(i+1) = K(i+1) XOR T1[K(i+2) XOR K(i) XOR C]
K(i+2) = K(i+2) XOR T1[K(i+3) XOR K(i+1) XOR C]
K(i+3) = K(i+3) XOR T1[K(i+4) XOR K(i+2) XOR C]
where i = 1 for rounds 1,5,9,13
5 for rounds 2,6,10,14
9 for rounds 3,7,11,15
13 for rounds 4,8,12,16.
Where the above formulas give K suffixes outside the range 1-16, the values
should be wrapped around, eg K17 = K1, K0 = K16.
C is a value based on the round number. For rounds 1,2,...,16 C has the value
0x00, 0x01,...0x0F
This is unwinding the effects of the round key manipulation in the decryption
algorithm.
Step Two - XOR key bytes with data bytes
----------------------------------------
This is simply:
d5 = K(i) XOR d5
d6 = K(i+1) XOR d6
d7 = K(i+2) XOR d7
d8 = K(i+3) XOR d8
where i = 1 for rounds 1,5,9,13
5 for rounds 2,6,10,14
9 for rounds 3,7,11,15
13 for rounds 4,8,12,16.
The reversing of the suffix values unwinds the interaction of key and data
bytes compared to the decryption algorithm.
Step Three - Perform the core function
------------------------------------------
First do 4 table lookups on Table 1:
d5 = T1(d5), d6 = T1(d6), d7 = T1(d7), d8 = T1(d
Then use Table 2 as follows '~' means 'swap nybbles':
d5 = d8 XOR d5
d7 = T2[(~d + d7]
d8 = d7 XOR d8
d6 = T2[(~d7) + d6]
d7 = d6 XOR d7
d5 = T2[(~d6) + d5]
Then use Table 1 as follows:
d6 = d5 XOR d6
d8 = T1[(~d5) + d8]
d5 = d8 XOR d5
d7 = T1[(~d + d7]
d8 = d7 XOR d8
d6 = T1[(~d7) + d6]
Finally do:
d7 = d6 XOR d7
d6 = d5 XOR d6.
This is identical to the decryption core function, but clearly it's 'working
in the opposite direction'.
Step Four - Get data values for the next round
-----------------------------------------------
SECA (PART 5)
These are obtained from Table 2 as follows:
d1 = T2(d6) XOR d1
d2 = T2(d XOR d2
d3 = T2(d5) XOR d3
d4 = T2(d7) XOR d4
Data values d1 and d5, d2 and d6, d3 and d7, d4 and d8 are then swapped ready
for the next round.
At the end of the 16th round this swap is not performed and the signature
total is d1,...,d8 which should equal the 8 bytes following the 0x82
parameter.
I know all this stuff looks pretty daunting, but if you follow it through with
an example, you'll soon see what's going on.
To summarise, we can say that control word decryption is Mediaguard DEcryption
but message signature is Mediaguard ENcryption. The keys stored are for direct
use with Mediaguard Encryption and in each round a round key R is generated
for that round.
So we can say that the Encryption algorithm operates on round keys
R1,R2,...,R16.
The Decryption algorithm is the reverse of Encryption; the purpose of the key
preparation stage is to generate R16. In each Decryption round a round key is
generated for the next round. The round keys for Decryption are
R16,R15,...,R1. The whole procedure ensures that Decryption is exactly the
reverse of Encryption.
By the way, if anyone recognises the algorithm and its name, perhaps they'd be
kind enough to let me know.
PIN CONTROLLED OPERATIONS
The Mediaguard system protects some transactions with a PIN code to ensure
that they are performed by the subscriber only. The command C1 30 handles PIN
controlled activity.
Three variations are possible
1) C1 30 00 00 10
is issued by the CAM following a dialogue with a subscriber who wants to
create or update their PIN. The card responds with '30' and receives
00 00 00 00 00 00 xx xx 00 00 00 00 00 00 yy yy
90 00
where xx xx and yy yy are the old and new PIN. If the old PIN is incorrect the
card returns 90 10.
2) The CAM issues
C1 30 00 01 09
when a subscriber wishes to change the Reference Maturity Rating. This time
the card receives
00 00 00 00 00 00 xx xx yy
90 00
where xx xx is the PIN and yy is the new Reference Maturity Rating.
3) The CAM issues
C1 30 00 02 09
when a subscriber wants to purchase something, eg a PPV programme or some
tokens for later use. Then the card receives
00 00 00 00 00 00 xx xx yy
90 00
where xx xx is the PIN and yy is an authorisation code. The authorisation code
permits the card to process a subsequent purchase transaction.
ENTITLEMENT MANAGEMENT
Entitlement Management messages are mainly implemented by the C1 40 command.
The facilities offered are rich and powerful, with far more flexibilty than
those in Eurocrypt. Some concepts remain however; updates may be to an
individual card, to a group of cards or to all cards just as in Eurocrypt.
Each card belongs to a SA (the first 3 bytes of the UA) with 256 members of a
SA as in Eurocrypt M; a SA bitmap of subscriber activity is also used to check
that a shared update is for an individual subscriber, using a CUSTWP byte
which is the last byte of the UA. The SA bitmap is conveyed in the C1 40
datastream however, which accounts for why these strings are much longer than
Eurocrypt. Remember in the latter, the SA bitmap is in a separate command
(CA F0).
All in all, the C1 40 command supports 33 parameters which permits a wide
variety of updates from single keys to complete providers. There are many more
options than Eurocrypt for deleting keys, packages, providers, PPV events and
subscriptions which must make it very difficult to 'switch on' an expired
card.
I will focus on the more common and interesting parameters.
If you look at a typical C1 40 command it could be
C1 40 19 82 35
and after the card responds with '40' the CAM sends a data stream like
96 E8 5D 3B 97 26 6E B1
82 0F 87 17 D3 5C 87 47
34 5E 39 79 2F 8E 84 4C
16 E2 3A 6A A3 40 30 C9
05 5F BB 01 56 11 7C 4F
BF 1F C3 32 21 BD 13 D9
60 53 25 CB 9E
90 00.
There's no discernible pattern in the packet because the data is encrypted
using Primary key 02 (and maybe Secondary key 02) for Provider 09. This
technique is called Superencryption and it means that encrypted data (such as
operation keys) is encrypted again before transmission. Superencryption is
used when the most significant bit of P2 is set in the C1 40 command, and it's
used to make it hard for anyone to understand what the data is, although
experienced hackers will know that it doesn't necessarily make the hacking
process any more difficult.
So the card takes each block of 8 bytes and decrypts it using the Mediaguard
decryption algorithm (leaving the last 5 bytes alone) to obtain a packet which
does have the usual structure. Typical parameters obtained in this way could
be:
0x21, 0x22 xx xx subscription
0x30, 0x32 xx xx xx PPV details
0x42, 0x43 xx xx xx xx of various sorts
0x41 xx xx xx xx UA
0x80 (8 bytes) package bitmap for provider
0x90 (9 bytes) primary key
0x91 (9 bytes) secondary key
0xd0 (16 bytes) provider label
0xf0 (32 bytes) SA bitmap
and finally
0x82 (8 bytes) message signature.
In addition, it is possible to use parameters 0xD1 (two encrypted control
words) and 0x87 (one encrypted control word) with C1 40. There are other
parameters as well which will delete a PIN, delete keys, PPV events and so on.
The two key parameters 0x90 and 0x91 contain a key index and 8 bytes of
encrypted key data which is decrypted using the Mediaguard decryption
algorithm as described earlier.
Updates may be addressed to all subscribers, a group of subscribers, or a
single subscriber depending on the values of the most significant 3 bits of
parameter P1 as described earlier. In each of the four cases the signature
hash buffer is initialised to a different value. The message signature for
C1 40 command is based upon the Mediaguard encryption algorithm also as
described earlier.
That completes the description of the mainstream functionality of Mediaguard;
I'll summarise next other features which are either of marginal interest or
need more work to understand.
OTHER FACILITIES
It is possible to see which keys are in a card by using the C1 34 command with
parameters 06 00 01 followed by C1 32 P1 00 12 repeatedly where P1 is the
provider number. However you'll need to know something of the internal record
structure to make sense of the results and key data is blanked out as 8 0xFF
bytes anyway.
It may be possible to send a command to the card which changes its mode so
that it has a slightly different ATR. In this mode the command C1 44 can be
used (and several others). These commands change the card's functionality and
allow alternative ways of doing things with some clever encryption. I'm not
clear whether the card mode is there to provide a built-in ECM capability or
for personalising, validation and testing purposes.
Finally, more work needs to be done to understand the exact minutiae of PPV;
when this is clear I'll update the document.
On a final note, if anyone publishes any software or web site information as
a result of reading this paper, perhaps they would do me the courtesy of
acknowledging this paper as their reference, and send me if possible, a copy
of their programs.
DATA ENCRYPTION STANDARD or DES (PART 1)
The U.S government in 1977 adopted the Data Encryption Standard (DES) algorithm. According to it’s developer the DES algorithm is:
“ It is a block cipher system which transforms 64-bit data blocks under a 56-bit secret key under a 56-bit secret key, by means of permutation and substitution.”
Now, this tutorial will guide you through the various steps of the DES encryption algorithm making you more confident in dealing with DES encryption.
The following is a step by step guide to the DES algorithm, which was originally written by Matthew Fischer and has been edited by me-:
1.) Firstly, we need to process the key.
1.1 Get a 64-bit key from the user. (Every 8th bit is considered a parity bit. For a key to have correct parity, each byte should contain an odd number of "1" bits.)
1.2 Calculate the key schedule.
1.2.1 Perform the following permutation on the 64-bit key. (The parity bits are discarded, reducing the key to 56 bits. Bit 1 of the permuted block is bit 57 of the original key, bit 2 is bit 49, and so on with bit
56 being bit 4 of the original key.)
Permuted Choice 1 (PC-1)
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
1.2.2 Split the permuted key into two halves. The first 28 bits are called C[0] and the last 28 bits are called D[0].
1.2.3 Calculate the 16 subkeys. Start with i = 1.
1.2.3.1 Perform one or two circular left shifts on both C[i-1] and D[i-1] to get C[i] and D[i], respectively. The number of shifts per iteration are given in the table below.
Iteration # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Left Shifts 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
1.2.3.2 Permute the concatenation C[i]D[i] as indicated below. This will yield K[i], which is 48 bits long.
Permuted Choice 2 (PC-2)
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
1.2.3.3 Loop back to 1.2.3.1 until K[16] has been calculated.
2 Process a 64-bit data block.
2.1 Get a 64-bit data block. If the block is shorter than 64 bits, it should be padded as appropriate for the application.
2.2 Perform the following permutation on the data block.
Initial Permutation (IP)
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
2.3 Split the block into two halves. The first 32 bits are called L[0], and the last 32 bits are called R[0].
2.4 Apply the 16 subkeys to the data block. Start with i = 1.
2.4.1 Expand the 32-bit R[i-1] into 48 bits according to the bit-selection function below.
Expansion (E)
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
2.4.2 Exclusive-or E(R[i-1]) with K[i].
2.4.3 Break E(R[i-1]) xor K[i] into eight 6-bit blocks. Bits 1-6 are B[1], bits 7-12 are B[2], and so on with bits 43-48 being B[8].
2.4.4 Substitute the values found in the S-boxes for all B[j]. Start with j = 1. All values in the S-boxes should be considered 4 bits wide.
2.4.4.1 Take the 1st and 6th bits of B[j] together as a 2-bit value (call it m) indicating the row in S[j] to look in for the substitution.
2.4.4.2 Take the 2nd through 5th bits of B[j] together as a 4-bit value (call it n) indicating the column in S[j] to find the substitution.
2.4.4.3 Replace B[j] with S[j][m][n].
Substitution Box 1 (S[1])
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S[2]
15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
S[3]
10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
S[4]
7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
S[5]
2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
S[6]
12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
S[7]
4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
S[8]
13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
2.4.4.4 Loop back to 2.4.4.1 until all 8 blocks have been replaced.
2.4.5 Permute the concatenation of B[1] through B[8] as indicated below.
Permutation P
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
2.4.6 Exclusive-or the resulting value with L[i-1]. Thus, all together, your R[i] = L[i-1] xor P(S[1](B[1])...S[8](B[8])), where B[j] is a 6-bit block of E(R[i-1]) xor K[i]. (The function for R[i] is written as, R[i] = L[i-1] xor f(R[i-1], K[i]).)
2.4.7 L[i] = R[i-1].
2.4.8 Loop back to 2.4.1 until K[16] has been applied.
2.5 Perform the following permutation on the block R[16]L[16].
Final Permutation (IP**-1)
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
This has been a description of how to use the DES algorithm to encrypt one 64-bit block. To decrypt, use the same process, but just use the keys K[i] in reverse order. That is, instead of applying K[1] for the first
iteration, apply K[16], and then K[15] for the second, on down to K[1].
Summaries:
Key schedule:
C[0]D[0] = PC1(key)
for 1 <= i <= 16
C[i] = LS[i](C[i-1])
D[i] = LS[i](D[i-1])
K[i] = PC2(C[i]D[i])
Encipherment:
L[0]R[0] = IP(plain block)
for 1 <= i <= 16
L[i] = R[i-1]
R[i] = L[i-1] xor f(R[i-1], K[i])
cipher block = FP(R[16]L[16])
Decipherment:
R[16]L[16] = IP(cipher block)
for 1 <= i <= 16
R[i-1] = L[i]
L[i-1] = R[i] xor f(L[i], K[i])
plain block = FP(L[0]R[0])
To encrypt or decrypt more than 64 bits there are four official modes (defined in FIPS PUB 81). One is to go through the above-described process for each block in succession. This is called Electronic Codebook
(ECB) mode. A stronger method is to exclusive-or each plaintext block with the preceding ciphertext block prior to encryption. (The first block is exclusive-or'ed with a secret 64-bit initialization vector (IV).) This is called Cipher Block Chaining (CBC) mode. The other two modes are Output Feedback (OFB) and Cipher Feedback (CFB).
When it comes to padding the data block, there are several options. One is to simply append zeros. Two suggested by FIPS PUB 81 are, if the data is binary data, fill up the block with bits that are the opposite of the last bit of data, or, if the data is ASCII data, fill up the block with random bytes and put the ASCII character for the number of pad bytes in the last byte of the block. Another technique is to pad the block with random bytes and in the last 3 bits store the original number of data bytes.
The DES algorithm can also be used to calculate checksums up to 64 bits long (see FIPS PUB 113). If the number of data bits to be check summed is not a multiple of 64, the last data block should be padded with zeros. If the data is ASCII data, the first bit of each byte should be set to 0. The data is then encrypted in CBC mode with IV = 0. The leftmost n bits (where 16 <= n <= 64, and n is a multiple of of the final ciphertext block are an n-bit checksum.
DATA ENCRYPTION STANDARD or DES (PART 2)
Wow, that was one heck of a paper on DES. That would be all you need to implement DES. Well, if you still have not understood how the DES algorithm is implemented, then I suggest you go through the following C program:
#include <stdio.h>
static int keyout[17][48];
void des_init(),lshift(),cypher(),des_encrypt (),des_descrypt();
void des_init(unsigned char *key){
unsigned char c[28],d[28];
static int pc1[56] = {57,49,41,33,25,17,9,
01,58,50,42,34,26,18,
10,02,59,51,43,35,27,
19,11,03,60,52,44,36,
63,55,47,39,31,23,15,
07,62,54,46,38,30,22,
14,06,61,53,45,37,29,
21,13,05,28,20,12,04};
static int pc2[48] = {14,17,11,24,1,5,
3,28,15,6,21,10,
23,19,12,4,26,8,
16,7,27,20,13,2,
41,52,31,37,47,55,
30,40,51,45,33,48,
44,49,39,56,34,53,
46,42,50,36,29,32};
static int nls[17] = {
0,1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1};
static int cd[56],keyb[64];
static int cnt,n=0;
register int i,j;
for(i=0;i<8;i++) /*Read in key*/
for(j=0;j<8;j++) keyb[n++]=(key[i]>>j&0x01);
for(i=0;i<56;i++) /*Permuted choice 1*/
cd[i]=keyb[pc1[1]-1];
for(i=0;i<28;i++){
c[i]=cd[i];
d[i]=cd[i+28];
}
for(cnt=1;cnt<=16;cnt++){
for(i=0;i<nls[cnt];i++){
lshift(c); lshift(d);
}
for(i=0;i<28;i++){
cd[i]=c[i];
cd[i+28]=d[i];
}
for(i=0;i<48;i++) /*Permuted Choice 2*/
keyout[cnt][i]=cd[pc2[i]-1];
}
}
static void lshift(unsigned char shft[]){
register int temp,i;
temp=shft[0];
for(i=0;i<27;i++) shft[i]=shft[i+1];
shft[27]=temp;
}
static void cypher(int *r, int cnt, int *fout){
static int expand[48],b[8][6],sout[8],pin[48];
register int i,j;
static int n,row,col,scnt;
static int p[32]={
16,7,20,21,29,12,28,17,1,15,23,26,
5,18,31,10,2,8,24,14,32,27,3,9,
19,13,30,6,22,11,4,25};
static int e[48] = {32,1,2,3,4,5,
4,5,6,7,8,9,
8,9,10,11,12,13,
12,13,14,15,16,17,
16,17,18,19,20,21,
20,21,22,23,24,25,
24,25,26,27,28,29,
28,29,30,31,32,1};
static char s[8][64] = {
14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7, /*s1*/
0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,
4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,
15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13,
15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10, /*s2*/
3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5,
0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15,
13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9,
10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8, /*s3*/
13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1,
13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7,
1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12,
7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15,/*s4*/
13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9,
10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4,
3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14,
2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9,/*s5*/
14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6,
4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14,
11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3,
12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11, /*s6*/
10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,
9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,
4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13,
4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1,/*s7*/
13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6,
1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2,
6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12,
13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7, /*s8*/
1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2,
7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8,
2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11
};
for(i=0;i<48;i++) expand[i]=r[e[i]-1]; /*Expansion Function*/
for(i=n=0;i<8;i++) {
for(j=0;j<6;j++,n++) b[i][j]=expand[n]^keyout[cnt][n];
}
/*Selection functions*/
for(scnt=n=0;scnt<8;scnt++){
row=(b[scnt][0]<<1)+b[scnt][5];
col=(b[scnt][1]<<3)+(b[scnt][2]<<2)+(b[scnt][3]<<1)+b[scnt][4];
sout[scnt]=s[scnt][(row<<4)+col];
for(i=3;i>=0;i--){
pin[n]=sout[scnt]>>i;
sout[scnt]=sout[scnt]-(pin[n++]<<i);
}
}
for(i=0;i<32;i++) fout[i]=pin[p[i]-1]; /*Permutation Function*/
}
static int p[64] = {58,50,42,34,26,18,10,2,
60,52,44,36,28,20,12,4,
62,54,46,38,30,22,14,6,
64,56,48,40,32,24,16,8,
5 = {58,50,42,34,26,18,10,2,
60,52,44,36,28,20,12,4,
62,54,46,38,30,22,14,6,
64,56,48,40,32,24,16,8,
57,49,41,33,25,17,9,1,
59,51,43,35,27,19,11,3,
61,53,45,37,29,21,13,5,
63,55,47,39,31,23,15,7};
static int invp[64]={
40, 8,48,16,56,24,64,32,39, 7,47,15,55,23,63,31,
38, 6,46,14,54,22,62,30,37, 5,45,13,53,21,61,29,
36, 4,44,12,52,20,60,28,35, 3,43,11,51,19,59,27,
34, 2,42,10,50,18,58,26,33, 1,41, 9,49,17,57,25};
void des_encrypt(unsigned char *input){
static unsigned char out[64];
static int inputb[64],lr[64],l[32],r[32];
static int fn[32];
static int cnt,n;
register int i,j;
for(i=n=0;i<8;i++)
for(j=0;j<8;j++) inputb[n++]=(input[i]>>j&0x01);
for(i=0;i<64;i++){ /*Initial Permutation*/
lr[i]=inputb[p[i]-1];
if(i<32) l[i]=lr[i];
else r[i-32]=lr[i];
}
for(cnt=1;cnt<=16;cnt++){ /*Main encryption loop*/
cypher(r,cnt,fn);
for(i=0;i<32;i++){
j=r[i];
r[i]=l[i]^fn[i];
l[i]=j;
}
}
for(i=0;i<32;i++){
lr[i]=r[i];
lr[i+32]=l[i];
}
for(i=0;i<64;i++) out[i]=lr[invp[i]-1]; /*Inverse IP*/
for(i=1;i<=8;i++)
for(j=1;j<=8;j++) input[i-1]=(input[i-1]<<1)|out[i*8-j];
}
void des_decrypt(unsigned char *input){
static unsigned char out[64];
static int inputb[64],lr[64],l[32],r[32];
static int fn[32];
static int cnt,rtemp,n;
register int i,j;
for(i=n=0;i<8;i++)
for(j=0;j<8;j++) inputb[n++]=(input[i]>>j&0x01);
for(i=0;i<64;i++){ /*Initial Permutation*/
lr[i]=inputb[p[i]-1];
if(i<32) l[i]=lr[i];
else r[i-32]=lr[i];
}
for(cnt=16;cnt>0;cnt--){ /*Main decryption loop*/
cypher(r,cnt,fn);
for(i=0;i<32;i++){
rtemp=r[i];
if(l[i]==1 && fn[i]==1) r[i]=0;
else r[i]=(l[i] || fn[i]);
l[i]=rtemp;
}
}
for(i=0;i<32;i++){
lr[i]=r[i];
lr[i+32]=l[i];
}
for(i=0;i<64;i++) out[i]=lr[invp[i]-1]; /*Inverse IP*/
for(i=1;i<=8;i++)
for(j=1;j<=8;j++) input[i-1]=(input[i-1]<<1) | out[i*8-j];
}
int main(int argc, char *argv[]){
unsigned char *key;
unsigned char data[8];
int n;
FILE *in;
FILE *out;
if (argc!=4) {
printf("\r\nUsage: des [e][d] <source file> <destination file>\r\n");
return 1;
}
key=(unsigned char*)getpass("Enter Key:");
des_init(key);
if((in=fopen(argv[2],"rb"))==NULL){
fprintf(stderr,"\r\nCould not open input file: %s",argv[2]);
return 2;
}
if((out=fopen(argv[3],"wb"))==NULL){
fprintf(stderr,"\r\nCould not open output file: %s",argv[3]);
return 3;
}
if(argv[1][0]=='e'){
while ((n=fread(data,1,8,in)) >0){
des_encrypt(data);
printf("data enctyted");
if(fwrite(data,1,8,out) < {
fprintf(stderr,"\r\nError writing to output file\r\n");
return(3);
}
}
}
if(argv[1][0]=='d'){
while ((n=fread(data,1,8,in)) >0){
des_decrypt(data);
if(fwrite(data,1,8,out) < {
fprintf(stderr,"\r\nError writing to output file\r\n");
return(3);
}
}
}
fclose(in); fclose(out);
return 0;
}ntf(stderr,"\r\nError writing to output file\r\n");
return(3);
}
}
}
fclose(in); fclose(out);
return 0;
}
HOW THE RSA CIPHER WORKS (RSA-KEYLIST, PART 1)
Prime Number Hide-and-Seek: How the RSA Cipher Works
Table of Contents
* Preface: What is This?
* Introduction: The Idea of a Trapdoor Function
* Background, Part I: How to Calculate with Exponents
* Background, Part II: Modulus Arithmetic
* Background, Part III: The Fundamental Theorem of Algebra
* Background, Part IV: Relatively Prime Numbers
* Euler's Totient Function
* Euler's Totient Theorem
* Variations on a Theme
* The Plot Thickens
* Does This Really Work?
* Making a Pair of Keys
* An Example
* How to Crack RSA
* How to Make RSA Uncrackable
* Huge Exponents in Modulus Arithmetic
* Safety in Numbers
* References
Preface: What is This?
The RSA cipher is a fascinating example of how some of the most abstract
mathematical subjects find applications in the real world. Few are the
mathematicians who study creatures like the prime numbers with the hope or
even desire for their discoveries to be useful outside of their own domain.
But every now and then that is exactly what happens.
This text explains the mathematics behind RSA -- how and why it works. The
intended audience is just about anyone who is interested in the topic and
who can remember a few basic facts from algebra: what a variable is, the
difference between a prime number and a composite number, and the like.
The most important mathematical facts necessary for understanding RSA's
foundations are reviewed near the beginning. Even if you are familiar with
everything covered in these sections, I would recommend that you at least
skim through them.
In one or two places, I have specifically targeted an explanation to what I
consider to be the average computer programmer, leveraging analogous
concepts in programming and general mathematics.
Before getting started, I should make some observations on the mathematical
notation used here.
For the most part, where notations for the same idea differ between
standard mathematics and the common practices among computer programmers, I
have stuck with the mathematicians. This is, after all, a mathematical
subject. However, I have deviated in a few places where there was too much
opportunity for confusion. I have used * to denote multiplication, and have
completely avoided "implied" multiplication (i.e., using PQ as shorthand
for P * Q). Since not all web browsers can display superscripts, I have
used ^ to denote exponentiation. (This necessitates more parenthesizing
than would normally be used.) The mathematician's three-bar congruency
symbol is not available, so I have made do with = instead. Variables are
always named with a single capital letter.
Finally, please note that throughout the text I use the word number to
refer specifically to a positive integer -- what are sometimes referred to
as the natural numbers, or counting numbers.
------------------------------------------------------------------------
Introduction: The Idea of a Trapdoor Function
What a mathematician refers to as a function is very similar to a function
in computer programming. It is, in essence, an abbreviation. For example:
F(X) = 7 * X + 43.
If X happens to be 3, then F(X) will be 64. So, "F(3)" is shorthand for
"7 * 3 + 43".
The same function in a C program might look like:
int F(int x)
{
return 7 * x + 43;
}
Of course, in a computer program, functions are used to encapsulate all
kinds of algorithms, and frequently make use of external variables and the
like. In mathematics, however, a function is used solely for the number it
returns. And, given a certain number as input, they will always return the
same output. (Thus, rand() would not qualify as a mathematical function,
unless it were written so that the seed value was passed in as an input
parameter.)
Mathematicians often consider how to construct a function's inverse --
taking a function and making a new one that "goes in the other direction",
so to speak:
G(X) = (X - 43) / 7.
G(64) is equal to 3, and in general, G(F(X)) is equal to X. Therefore, G is
F's inverse. Not all functions are invertible, of course. Clearly, the
function:
F(X) = X * 0
cannot be inverted. (Because how could G(F(X)) return X when F(X) is always
zero?)
Usually, when you have a mathematical function for which an inverse does
exist, constructing it is not too difficult. In fact, it is often
transparent. Typically, you can just run through the steps backwards,
subtracting where the original function adds, and so on. But can it be done
for every invertible function?
To put the question in terms of programming, imagine that there are two
functions:
int foo(int x);
int bar(int x);
foo() and bar() work like mathematical functions -- they do nothing but
compute a return value, and given the same number for input, they will
always produce the same output. (And pretend for the moment that this is on
a machine where integers can be arbitrarily large.) Suppose you are told
that bar() is the inverse of foo(). The statement:
x == bar(foo(x))
is always true, as long as x meets foo()'s requirements for a valid
argument.
Now, imagine that you have the source code for foo(), but not for bar().
Can you write your own replacement for bar(), just by examining foo()?
It seems that you ought to be able to. There are no secrets as to what
foo() does, after all. You can run foo() with different inputs as many
times as you like. You already know that bar() exists, somewhere, so you
that it is possible to write. Is it guaranteed that you can reconstruct it?
Theoretically speaking, the answer is yes. Given such an function, it is
always possible to construct its inverse. However, if we also throw in the
tiny constraint that you have to finish before the heat-death of the
universe, the answer subtly changes.
There are some special functions that, though what they do is simple
enough, and how they do what they do is utterly transparent, figuring out
how to undo what they do is a diabolical task. Such a creature is a
trapdoor function. Anyone can fall through a trapdoor, but only those who
know where the hidden lever is can climb back out again.
In 1975, Whitfield Diffie, Martin E. Hellman, and Ralph Merkle realized
that a trapdoor function could be the basis for an entirely new kind of
cipher -- one in which the decoding method could remain secret even when
the encoding method was public knowledge. Diffie and Hellman published a
paper in 1976 that described this idea, and offered some examples of weak
trapdoor functions. And in 1977, Ronald L. Rivest, Adi Shamir, and Leonard
Adleman outlined, in an MIT technical memo, an excellent candidate that
became the basis for the RSA cipher.
What follows is a description of that function.
Posting Permissions
