XOR is + (and -) in modulo 2 arithmetic. So when you are doing arithmetic in GF(2^p) (Galois Field with 2 ^ power p elements), all the arithmetic will be modulo 2.
This ties into question 2. We use modulo in cryptography for the same reason that it is used to create pseudo-random numbers. Once we have applied the various block ciphers using modulo arithmetic to a message, one can't really tell the difference between that and a random number.
  To generate a pseudo-random number using modulo, you start with a seed value and apply some operations on it to make another value that SEEMS to have no relationship to the seed and thus seems to be random.
   If instead of using some arbitrary seed, we use a message that we wanted to encrypt, did a similar kind of sets of operation (but with the proviso that each operation was reversible), then kept track of these operations with a key, we would have a cryptographic transform.
  A useful analogy that Bruce Schnierer prepared for the Novel Cryptomicon uses a pack of playing cards as a way of storing an encrypted message.
  Match each letter of a message to a particular card in the deck (assuming suit order club, diamonds, hearts, spades). Ace-clubs <->A, 2C <->B ... K diamonds <->Z, Ace Hearts <->a, 2 hearts <-> b .... Order the deck according to the message.
Then take a binary number as key. Read the binary number from least significant digit to most. If the digit is 0, cut the card deck in half, if the card deck is one, do a perfect shuffle (mixing lower half with upper half). Now the deck (if the key is long enough) will be very well shuffled from the original order. Send the key in a secure manner to the message recipient. Send the deck by ordinary mail.
  Without the key, it would be almost impossible to recover the original message, with the key, we can reverse the order of shuffles and cuts and get the message back.
   This is essentially how block ciphers work, but the shuffles and cuts are done on a computer.

Modulo arithmetic IS used to keep things in range, but it is also used because it has many nice mathematical properties.
   The main one is that numbers modulo a prime form a field, a mathematical object that has the property that the operations of addition, subtraction, multiplication, division, power and log on members of the field have results that are also members of the field. Ordinary integers don't have this property. There is no integer that is equal to 5/7.
   The Public key encryption algorithms work because, although it is fairly easy to raise a number x power y =z mod (n prime) in a finite field, it is hard to find log(base x)(z) (find, y given z and x and n) which is used for Diffie-Helman. It is also hard to find the factors of a number n which is the product of 2 large primes p and q (n=p*q), which is used in RSA encryption.

RSA and Diffie-Helman differ on how they use modular arithmetic but they are both public key cryptography. Diffie-Helman cannot be used to encrypt messages, but it can, and is, used to exchange keys.
   It works this way.
Alice and Bob agree on a large prime number n and a number g that is primitive mod n (primitive means that g^1, g^2, g^3 ... g^(n-1) are all different so generate all numbers < n).

Alice chooses a large integer x and sends Bob X=g^x (mod n).
Similarly Bob chooses a large integer y and sends Alice Y=g^y (mod n).
(neither has send little x or little y).

if Bob generates a key k=X^y mod n (k=g^(x*y) mod n)
and Alice generates k1= Y^x mod n. (k1 =g (y*x) mod n)

k and k1 will be the same number, but neither has given the other their private x or y.

Thus they exchange keys safely.

RSA depends on difficulty of factoring large numbers.

If we choose an encryption key e so that e and (p-1)*(q-1) are relatively prime (have no factors in common except 1), then we can generate another key d (using the Extended Euclid Algorithm [the Ancient Greek Euclid]) so that
 e*d = 1 mod (p-1)*(q-1) or d = (1/e) mod (p-1)(q-1).

E and n become public, d is kept private.

To encrypt a message M, consider it as a number, then divide it into blocks m[i]of digits less then number of digits in n.
Take c[i]=m[i]^e mod n for all the blocks. c[1]c[2]... is the encrypted message.
send the message.
   The recipient (who is the only one with private key d) calculates
  d[i]=c[i]^d (mod n) and this is the original m[i] since
  c[i]^d (mod n) == (m[i]^e)^d (mod n) == m[i]^{e*d) (mod n) == m[i]^( j*(p-1)*(q-1)+1)
== (m[i]^1)*(m[i]^(j*(p-1)*(q-1))) .
  but according to Fermat's little theorem and Eulers's generalization
  any integer x raised to power (p-1)*(q-1) mod n (where n=p*q) is equal to 1.
  so our calculation

 (m[i]^1)*(m[i]^(j*(p-1)*(q-1))) == m[i]^1 == m[i] and our original message is returned.

 Now you can see that public key encryption requires a lot of calculation of powers of large numbers. Also to use the RSA we need to get the parts of the key (n and e) to the recipient. That is where Diffie-Hellman helps RSA.

Knapsack algorithms are based on the problem of filling a knapsack to an exact weight s given a number of different integer valued weights b1,b2...bn .
What we have to do is find some subset of all the weights so that sum(bi, bi is in chosen set)=s.
Merkle-Hellmand restricted the sets of weights to a super-increasing set.
A super increasing set has property that given x1 <x2 <..< xn
xj>(x1+x2+...+x[j-1]) (each new weight weighs more than earlier ones combined).
In this case, there is a easy solution to the knapsack problem but adding the heaviest weight that fits, subtracting its weight from s and trying again.

  By disguising this super-increasing set in a larger set of weights, it was thought that the hard general knapsack problem would hide the easier version and could be used to hide a message.

Elliptic Curve algorithms work using quadratics rather than simple integers. They use less arithmetic for the same amount of security.

-----Original Message-----
From: David Hawley [mailto:chiman@hawaiian.net]
Sent: Wed December 05 2001 22:21
To: cisspstudy@securityfocus.com
Subject: RE: WELCOME to cisspstudy@securityfocus.com

O.K.

Hello out there. I'm taking on the most difficult (for me) chapter first,
cryptography
(in the WILEY CISSP Prep Guide). Here are the things that stump me so far:
(I don't really
think algebraically, not having taken Calculus... so if you can explain them
w/o using algebraic equations I would be grateful)

1) What is the point of using an XOR so often? Does it make things more
cryptic? Or is there
some special significance of the properties of an XOR? I understand the
basic meaning of an
XOR. 1 : 0 == 1, 1 : 1 = 0, 0 : 0 = 0, 0 : 1 = 1 so what does that have to
do with Cryptography?

2) The only use of modulo in programming, prior to this, I have seen is for
generating random
numbers.... is the point of using modulo in these functions such that the
values of the bits
pre and post encryption are in the same range? For example with the simple
Caesar encryption
we have an alphabet of 26 characters, with a key of 6 for example every
encrypted value would
be above 6, except for the last 6 letters of the alphabet, and because we
use modulo, they end
up using the first 6 values.... does that make sense?

3) When using the RSA 128 bit encryption in Netscape (to and from a https
server) does it
actually use a Diffie-Hellman key exchange?

4) In Merkle-Hellman what is a knapsack? and what kind of "weight" are they
talking about? Does
weight refer to the size or "greatness" of the number? They don't define
knapsack or weight.

5) What is the point of using an Elliptic Curve in PKI?

TIA, David

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]