Encryption & Prime Numbers

MisterX b.xavier at internet.lu
Tue Sep 7 02:43:13 EDT 2004

the 32 bit word is just a long word...
bitXOR is used as a small time encryption. Just bitxor any number, you
will get aonther number. If you reverse the operation, you get your
number back. The bitXOR function is limited to 2^48-1 or 2^64-1.

If you use a non-prime number, it's possible that you get multiple numbers
that can unlock this number. BitXOR is extremely weak since the number
of attacks is quite small. In RSA, they started with (approx.) 2^56 bit
primes, then 2^128, and they way higher now, 2^4096 possibly.

Random padded cypher blocks are just padding to fool the cracker into
thinking he's attacking real data - usually. There's 20 million different
types of pading possible to make their lives an eternity but these guys
can use almost any resources! ;)

The private key systems use an obscure elliptical geometry topology
which is also used solve the problem or crack the key. The ellipse allows
to have 2 answers for any points on the curve of an ellipse. 

Here's more information on how it works.

and a few more links here

Note that cryptography is a wide and deep subject, too many links or
code to make sense of ;)

Hope that helps.

> At 17:23 06/09/2004 -0700, Mark Brownell wrote:
> >from here:
> >http://www.guardian.co.uk/uk_news/story/0,3604,1298728,00.html
> >
> >I fail to see the relationship between a 32 bit word, bitXOR, and random 
> >padded cypher block chaining having to do anything with Prime Numbers. As 
> >far as Blowfish goes there doesn't look like there are any connections to 
> >prime numbers. Perhaps AES openSSL 128 bit encryption is based on random 
> >prime numbers. Any guesses as to how the above information can be 
> >considered useful beyond the scope of it being a new internet urban legend?
> Don't know about Blowfish specifically; it's a private-key algorithm, so 
> may have no requirement on primes.
> In general public/private key systems depend on the inability to decompose 
> very large numbers into their prime factors. So to generate a suitable 
> private key, you generate a number of primes, and multiply them together; 
> if someone could easily decompose that, they would be a large part of the 
> way towards discovering your private key.
> More mathematically, but less understandably ...
> >RSA is a public-key cryptosystem for both encryption and authentication; 
> >it was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. It 
> >works as follows: take two large primes, p and q, and find their product n 
> >= pq; n is called the modulus. Choose a number, e, less than n and 
> >relatively prime to (p-1)(q-1), which means that e and (p-1)(q-1) have no 
> >common factors except 1. Find another number d such that (ed - 1) is 
> >divisible by (p-1)(q-1). The values e and d are called the public and 
> >private exponents, respectively. The public key is the pair (n,e); the 
> >private key is (n,d). The factors p and q maybe kept with the private key, 
> >or destroyed.
> >
> >It is difficult (presumably) to obtain the private key d from the public 
> >key (n,e). If one could factor n into p and q, however, then one could 
> >obtain the private key d. Thus the security of RSA is related to the 
> >assumption that factoring is difficult. An easy factoring method or some 
> >other feasible attack would "break" RSA.
> >
> >Here is how RSA can be used for privacy and authentication (in practice, 
> >the actual use is slightly different:
> >
> >RSA privacy (encryption): Suppose Alice wants to send a message m to Bob. 
> >Alice creates the ciphertext c by exponentiating: c = me mod n, where e 
> >and n are Bob's public key. She sends c to Bob. To decrypt, Bob also 
> >exponentiates: m = cd mod n; the relationship between e and d ensures that 
> >Bob correctly recovers m. Since only Bob knows d, only Bob can decrypt.
> >
> >RSA authentication: Suppose Alice wants to send a message m to Bob in such 
> >a way that Bob is assured that the message is authentic and is from Alice. 
> >Alice creates a digital signature s by exponentiating: s = md mod n, where 
> >d and n are Alice's private key. She sends m and s to Bob. To verify the 
> >signature, Bob exponentiates and checks that the message m is recovered: m 
> >= se mod n, where e and n are Alice's public key.
> >
> >Thus encryption and authentication take place without any sharing of 
> >private keys : each person uses only other people's public keys and his or 
> >her own private key. Anyone can send an encrypted message or verify a 
> >signed message, using only public keys, but only someone in possession of 
> >the correct private key can decrypt or sign a message.
> (quote from www.anujseth.com)
> -- Alex.

More information about the use-livecode mailing list