cryptography notes:
First, some vocabulary. Let's say you have information stored in an
electronic format. It doesn't have to be text, but for the sake of this
tutorial, let's say we have a top-secret text file. This original data that
can be read and understood without any special measures is
called plaintext (or cleartext.) The method of disguising plaintext in such
a way as to hide its substance is called encryption. The encrypted (and
therefore unreadable) plaintext is called ciphertext. The process of
reverting ciphertext to its original plaintext is called decryption.
Here's an illistration:
plaintext -->[encryption]-->ciphertext-->[decryption]-->plaintext
(source: http://www.pgpi.org/doc/pgpintro/ )
Cryptography, then, is the science of encrypting and decrypting data, of
securing it.Cryptanalysis is the science of analyzing and breaking secure
communications. Classical cryptanalysis involves an interesting
combination of analytical reasoning, application of mathematical tools,
pattern finding, patience, determination, and luck.
Cryptology embraces both cryptography and cryptanalysis.
A cryptographic algorithm, or cipher, is a mathematical function used in
the encryption and decryption process. A cryptographic algorithm works in
combination with a key -- a word, number, or phrase -- to encrypt the
plaintext. The same plaintext encrypts to different ciphertext with
different keys. The security of encrypted data is entirely dependent on
two things: the strength of the cryptographic algorithm and the secrecy of
the key.
A cryptographic algorithm, plus all possible keys and all the protocols
that make it work comprise a cryptosystem. PGP is an example of a
cryptosystem.
In conventional cryptography, also called secret-key or symmetric-key
encryption, one key is used both for encryption and decryption. The Data
Encryption Standard (DES) is an example of a conventional cryptosystem that
is widely employed by the Federal Government. Here is an illustration of
the conventional encryption process:
plaintext -->[encryption with KEY A]-->ciphertext-->[decryption with KEY
A]-->plaintext
An extremely simple example of conventional cryptography is a substitution
cipher (think "cereal box decoder rings.") A substitution cipher substitutes
one piece of information for another. For example, a simple algorithm is to
offset the letters in the alphabet. In this case the key is the number of
characters that are shifted.
As an illustration, if we encode the word "SECRET" using a shift(key) of 3,
we offset the alphabet so that the 3rd letter down (D) begins the alphabet.
So starting with
ABCDEFGHIJKLMNOPQRSTUVWXYZ
and sliding everything up by 3, you get
DEFGHIJKLMNOPQRSTUVWXYZABC
where D=A, E=B, F=C, and so on.
Using this scheme, the plaintext, "SECRET" encrypts as "VHFUHW." To allow
someone else to read the ciphertext, you tell them that the key is 3.
Here are some substitution cipher decoder pages: (The Caesar cipher is a
type of substitution cipher)
http://codebrkr.infopages.net/caesar.htm
http://www.woodmann.com/fravia/caesacy.htm
http://condor.depaul.edu/~mschaefe/IPD/caesar.html
To make the tranisition from the alphabet to numbers(so we can do math
on them), recall that in order to be stored by a computer, each letter of the
alphabet is represented by a number. In computers, letters are matched
with an ASCII character, (which is one byte (8 bits) long and can therefore
encode 256 letters.) Obviously, we don't have that many characters, even
when including upppercase and lowercase, numbers, and punctuation. The
rest of the 256 is taken up by special system codes and foreign characters,
etc. Now-a-days, FYI, letters can be encoded with unicode, which allows a
much larger encoding.
We've covered simple subsitution ciphers. Now let's talk about public key
cryptography. Public key cryptography is ubiquitious because, unlike
substition cipers, it is very difficult to break.
Public key cryptography is an asymmetric scheme that uses a pair of keys
for encryption: a public key, which encrypts data, and a corresponding
private, or secret key for decryption. You publish your public key to
the world while keeping your private key secret. Anyone with a copy of
your public key can then encrypt information that only you can read. Even
people you have never met.
It is computationally infeasible(that is, it's very hard) to deduce the
private key from the public key. Anyone who has a public key can encrypt
information but cannot decrypt it. Only the person who has the corresponding
private key can decrypt the information.
So Bob wants to send Alice a private message. He knows Alice's PUBLIC key,
so he is able to encrypt the message, which he sends to Alice. Alice then
uses her PRIVATE key to decrypt that message.
plaintext -->[encrypt with PUBLIC key]-->ciphertext-->[decrypt with PRIVATE key]-->plaintext
The primary benefit of public key cryptography is that it allows people who
have no preexisting security arrangement to exchange messages securely. The
need for sender and receiver to share secret keys via some secure channel is
eliminated; all communications involve only public keys, and no private key
is ever transmitted or shared.
A key is a value(a number, or pair of numbers) that works with a cryptographic
algorithm to produce a specific ciphertext. Keys are basically really, really,
really big numbers. Key size is measured in bits; the number representing a
1024-bit (remember the post concerning binary numbers?) key is darn huge. In
public key cryptography, in general, the bigger the key, the more secure the
ciphertext.
While the public and private keys are mathematically related, it's very difficult
to derive the private key given only the public key; however, deriving the
private key is always possible given enough time and computing power. This
makes it very important to pick keys of the right size; large enough to be
secure, but small enough to be applied fairly quickly. Additionally, you
need to consider who might be trying to read your files, how determined
they are, how much time they have, and what their resources might be.
How does public key encryption work?
There are several methods, but the most commonly used one is known as RSA.
To generate a pair of keys the procedure is:
1- pick two large random prime numbers P and Q
2- multiply them together: N = P * Q
3- Using Euler Totient Function, F(N) = (P - 1) * (Q - 1), determine E, D such that: E * D = 1 mod F(N)
4- E is your public key, D is your private key
5- Encrypted Message (C) = ME mod N
6- Decrypted Message (M) = CD mod N
[quick modulo(mod) arithmetic review: mod means remainder, so 5 mod 2 is 1.
In math terms this means: If a mod n = b, then a = c
For Example,
1- let's pick P = 7 and Q = 11
2- that means that N = P * Q = 77
3- and that F(N) = (P-1) * (Q-1) = 60
4- Determine E, D (key pair) such that E * D = 1 mod 60:
4a- Pick prime number (D) relatively prime to 60, e.g., 37
4b- Find E, where 37 * E = 61, 121, 181, 241, ...,
481 = 37 * 13
8 * 60 + 1 = 480 + 1
481 mod 60 = 1 mod 60
E = 13
Given Message (M) = 27, what is Encrypted Message (C) ?
C = ME mod N
C = 2713 mod 77 = 48
Given Encrypted Message (C) = 27, what is the Message (M) ?
M = CD mod N
M = 4837 mod 77 = 27
(source: http://ac.mit.edu/classes/presentations/presentations/PKI/tsld038.htm )
(see also: http://www.maths.mq.edu.au/~rody/math237/RSA.pdf )
(see also: http://world.std.com/~franl/crypto/rsa-example.html )
(see also: http://homepages.gold.ac.uk/rachel/RSA%20example.doc )
(see also: http://www-users.aston.ac.uk/~blowkj/internetworks/lecture14/sld015.htm )
The security of a public key system depends on the fact that it is difficult
to calculate the private key from the public key. In the system described
above, it is necessary to factor N to find x and y. Factorization is
believed to be difficult.
The main difficulty with public key encryption is getting the public key
of the person you want to communicate with. On a small scale, users can
simply give their public keys to each other in person, but this is impractical
on an internet-wide basis. One possible solution is for users to register
their public keys in directories which can be queried. This approach has
its own set of problems though. How do you know which directory the person
you want to communicate is registered with? If there are only a few central
directories they will rapidly become overloaded. If the directory service is
down or unreachable you can't send a message, even though there may be nothing
wrong with the network between you and the person you want to talk to.
The ideal solution would seem to be for the user to send you their public key
as part of the communication, but this has a chicken and egg problem: you can't
be sure that you're talking to the real user until you have their public key
to perform some sort of authentication, but you can't trust that they're who
they claim to be and are giving you the right public key until you can authenticate
them. Suppose A is trying to communicate with B, but it's really C on the other
end of A's connection. C could claim to be B but send C's public key. The
challenge-response protocol would work exactly as above, but A would be
talking to C instead of B. (this is a variation of a "man-in-the-middle attack")
The solution to this problem is to use certificates and certifying authorities
(think Verisign or Thawte.)
A certificate is a message containing your public key, digitally signed by a
trusted third party - the certificate issuer. To obtain a certificate you visit
a certificate issuer with whatever form of identification they require. They
produce a message which contains something like
Name: fred@foo.bar.edu
Public key: AF43D921CB812FA7
and digitally sign it with their public key. When someone wants to communicate
with you, you send them this certificate and, as long as they know the certifying
authority's public key, they can check the signature on the certificate and
extract your public key. It is not necessary to know the public key of every
certifier, because certifiers can create certificates for other certifiers.
For example, the departmental computing staff could get a certificate for their
public key and then issue certificates to users signed with the department's key.
The user would send a certificate chain to authenticate themselves - i.e. they
would send the department's certificate, signed by the certifying authority, to
tell the person on the other end what the department's key was, and their
certificate, signed by the department, to tell the other end what their public
key was.
Although the above sounds complicated, most of it can be handled automatically
behind the scenes. Web browsers, for example, come with the public keys of the
major certifying authorities compiled into them. If they receive a certificate
signed by an authority they don't know about then, as long as that certificate
is accompanied by another certificate signed by an authority they do know about
that authenticates it, they can add the new public key to their list and
authenticate users whose certificates have been signed by the new authority from then on.
Public key encrpytion is generally too slow to be used for extended exchanges,
so once the ends of a connection have authenticated themselves to each other,
a random symmetric key is generated and sent via public key encryption. This
key is then used to encrypt the connection with a faster, symmetric cipher.
(source: http://www.see.ed.ac.uk/it/online/memos/pkey.html )
(see also: http://www-users.aston.ac.uk/~blowkj/internetworks/lecture14/sld016.htm )
(see also: http://www-users.aston.ac.uk/~blowkj/internetworks/lecture14/sld017.htm )
(see also: http://www-users.aston.ac.uk/~blowkj/internetworks/lecture14/sld018.htm )
(see also: http://www-users.aston.ac.uk/~blowkj/internetworks/lecture14/sld019.htm )
-------------------------------------------
Information security (CIA)
a.. (C) Confidentiality: only intended receivers get the info
b.. (I) Integrity: intended receiver can verify whether message has been altered
during transmission
c.. (A) Authentication: intended receiver can verify the identity of the sender
d.. Non-repudiation:
e.. Availability and legitimate use:
Encryption Decryption
Plaintext -----------------------------> Ciphertext ------------------------------->
Plaintext
What you know: passwords, etc.
What you have: biometrics(fingerprint/retinal scan), physical key
Encryption: symmetric, asymmetric
Symmetric technology
a.. Substitution (ROT 13)
a.. Character to character
a.. System
b.. Random
b.. Character to code
b.. Transposition (construct a message as a matrix, and then transpose it):
Plaintext: Let's have dinner tonight
C A T
L E T
S H A
V E D
I N N
E R T
O N I
G H T
Send columns by alphabetic order of CAT
Ciphertext: EHENENHLSVIEOGTADNTIT
Decrypting: CAT is 3 long, 24 letters of ciphertext, every 8 in a column
a.. character stuffing (after certain number of characters, insert a certain
number of random characters
transposition and symmetric requires pre-transaction information (doesn't support
spontaneous(non pre-transaction information) encryption like e-commerce needs
symmetric and transposition are "secret-key" based
a.. asymmetric is called public-key or dual-key based
a.. everyone has a public and a private key
b.. with respect to a particular key pair, one key cancels the other
c.. given one key we cannot calculate the other key
http://ironbark.bendigo.latrobe.edu.au/subjects/int21cn/lectures/l17.d/Lect17.html
encrypting with your private key authenticates yourself to others (digital signature)
if you want both, first encrypt it with your private key and then encrypt that with
the intended recipient's public key
non-repudiation: prevent people from backing out of contracts by having a third
party make record of a double encrypted email
symmetric: use same key to encrypt and decrypt (DES, PGP). Potential use of multiple
keys, need for frequent key changes
-------------------
http://ironbark.bendigo.latrobe.edu.au/subjects/int21cn/lectures/l17.d/Lect17.html
RSA public / private key encryption
===============================================* Choose two large prime numbers, p
and q.
* compute n = p * q and x = (p-1)*(q-1)
* Choose a number relatively prime to x and call it e. This means that e is not a
prime factor of x or a multiple of it.
* Find d such that e * d = 1 mod x.
To use this technique, divide the plaintext (regarded as a bit string) into blocks
so that each plaintext message P falls into the interval 0 <= P < n. This can be
done by dividing it into blocks of k bits where k is the largest integer for which
2k < n is true.
To encrypt: C = P^e (mod n)
To decrypt: P = C^d (mod n)
The public key, used to encrypt, is thus: (e, n) and the private key, used to
decrypt, is (d, n))
RSA Example -- Key Generation
To create the public key, select two large positive prime numbers p and q p = 7, q
= 17
Compute (p-1) * (q-1)= 6x16= x = 96
Choose an integer E which is relatively prime to x E = 5
Compute n = p * q=7x17= n = 119
Kp is then n concatenated with E Kp = 119, 5
To create the secret key, compute D such that (D * E) mod x = 1 Ks = 119, 77
RSA Example -- Encryption and Decryption
private key: (n,e) = (119,5)
public key: (n,d) = (119,77)
To compute the ciphertext C of plaintext P, treat P as a numerical value
P = 19
mod is the same as remainder
19^5 mod 119 => 19^5=2476099, 2476099/119=20807.55462, so 119x20807=2476033,
and 2476099-2476033=66, so the
remainder or modulo is 66
C = P^E mod n Cipher text(C) = 66
To compute the plaintext P from ciphertext C:
P = C^D mod n P = 19
66^77 mod 119
66^77
127316015002712725024996823827450919411351129158643807873318778077633686286816610254398613549028148573790434899358326117107662397756833529856
----------------------------------------
secure websites (those whose addresses begin with https)
https stands for secure HyperText Transfer Protocol
Instead of transferring web information using plain text,
HTTPS encrypts the data using the SSL (Secure Socket Layer) protocol
SSL is also used to refer to Transport Layer Security (TLS), its successor.
1-- to establish the connection, the client (your browser) sends a ClientHello message containing
list of cipher suites, compression methods and the highest protocol version it supports.
as well as some random bytes
(see: http://en.wikipedia.org/wiki/Secure_Socket_Layer )
2--the server received the ClientHello, and sends a ServerHello, in response,
wherein the server chooses the connection parameters from the choices offered by the client.
3-- now that the connection parameters are agreed upon, the client and server exchange certificates
a certificate (specifically, a public key certificate) is a certificate which uses a digital signature
to bind together a public key with an identity . information such as the name of a person or an
organization, their address, and so forth. The certificate can be used to verify that a public key
belongs to an individual.
(see: http://en.wikipedia.org/wiki/Public_key_certificate )
Typically (in a PKI scheme,) the signature will be of a CA (certificate authority.)
CAs are SSL certificate providers
Examples of CAs are thawte, verisign, InstallSSL.
public key infrastructure (PKI) is an arrangement which provides for third-party vouching for user identities.
Validating the Certificate Authority is important to prevent "man in the middle" attacks
Man-in-the-middle attacks occur when the communication is intercepted en route.
This is where an unauthorized program sends its own certificate back to the client and
makes a client request to the server. Rather than the client and server validating with
each other they are validating with the unauthorized program.
(see: http://www.ourshop.com/resources/ssl_step2.html )
the client checks the certificate to ensure the name on the certificate matches the domain name the browser
requested the cert from. The certificate expiration date and valid certificate authority are also checked.
The client now creates a "premaster secret" that will be used to encrypt the rest of the session.
This is a random key that it encrypts using the agreed upon encryption method combined with the
server's public key string that it recieved and sends the new encrypted secret string back to the server
(see http://www.ourshop.com/resources/ssl_step3.html )
With the new "premaster secret" string, both the browser and the web site server create a new
"master secret" string and use it to create session keys (long strings of generated characters)
that their encryption programs use for the rest of the session to scramble and descramble
(or encrypt/decrypt) all transmissions for the rest of the session. With the Master Secret key
in place, both sides are also able to verify that the data didn't change in route.
The browser now has the information it needs to establish secure communication and it sends a
message to the server saying that it will start using the new session key.
|
| Web hosting by Utah Hub * Powered by CreativeTap * In association with Segomo |