PureBasic Forums - English

ahh the trick is
z=a^(x+k(p-1)) mod p = (a^x mod p .a^k(p-1) mod p) mod p = a^x mod p
using Fermat's little theorem
so well if u know p, writing a nice table for all z's which have an x as solution aint too hard

and if its diffie hellman then it's the reverse

anyone knows the standard values of the generator and the primes used by DH?

search for diffie hellman in the tips area this thread led to another that followed right through

1. Okie so we can compute mod fast enuf/and all sort of math actually
2. RSA does the following:
enrypted message=M^e mod n (n is a product of 2 primes, p and q)
M is message
Decrypted message=(M^e mod n)^d mod n = M^ed mod n = M mod n =M

M has to be smaller than n
e is the exponent, e and n are well known
d has to be chosen so that it satisfies the same
From the material I refer to:

We demonstrate the correctness of the deciphering algorithm using an identity due
to Euler and Fermat: for any integer (message) M which is relatively prime to n,
M^phi(n) mod n= 1 (mod n)
Here phi(n) is the Euler totient function giving number of positive integers less than n
which are relatively prime to n. For prime numbers p,
phi(p) = p - 1 :
In our case, we have by elementary properties of the totient function:
phi(n) = phi(p). phi(q)
= (p - 1) . (q - 1)
= n - (p + q) + 1 :
Since d is relatively prime to phi(n), it has a multiplicative inverse e in the ring of integers modulo phi(n):
e . d = 1 (mod phi(n))
We now prove that equations (1) and (2) hold (that is, that deciphering works
correctly if e and d are chosen as above). Now
D(E(M)) = (E(M))^d = (M^e)^dd (mod n) = M^ed (mod n)
E(D(M)) = (D(M))^e = (M^d)^e (mod n) = M^ed (mod n)
and
M^e.d = M^(kphi(n)+1) (mod n) (for some integer k):
7
we see that for all M such that p does not divide M
M^p-1 = 1 (mod p)
and since (p - 1) divides phi(n)
M(kphi(n)+1) = M (mod p):
This is trivially true when M = 0 (mod p), so that this equality actually holds for
all M. Arguing similarly for q yields
M(kphi(n)+1) = M (mod q) :
Together these last two equations imply that for all M,
M^ed = M(kphi(n)+1) = M (mod n):
This implies (1) and (2) for all M; 0 =M < n. Therefore E and D are inverse
permutations.

thanks for the explanation alokdube

well simple dabling, how do we break the above? compute all possible "d" for given n and "e" so that
a^ed mod n = a mod n ?

note that the above eqn is independent of "a"
because the message can be anything.

alokdube wrote:well simple dabling, how do we break the above? compute all possible "d" for given n and "e" so that
a^ed mod n = a mod n ?

Sorry, asking me about such things, is about as useful as talking to a cow chewing on some grass. You'll get a bit of wind out the rear but thats about it. the brain is mostly idle

alokdube wrote:well simple dabling, how do we break the above? compute all possible "d" for given n and "e" so that
a^ed mod n = a mod n ?

alokdube wrote:note that the above eqn is independent of "a"
because the message can be anything.

In modular arithmetic exponentiation inverses (called discrete logarithms) are not easy to find!

What does this mean? A one-way function!

Good luck.

yes but
((a^e)mod n)^d mod n =a mod n
is what we have to compute
put a=2
we can compute 2^e mod n =C ?
so we essentially can say , to compute d given n and C so that:
C^d mod n = 2 mod n

this should be easier to do, or not?

well so we have:
e.d =1 mod m
i.e
e.d - km =m
given we know e and m , we have to compute d and k, sounds like a simple job anyways

e.d = 1 mod m
e.d -k.m =1
we know e, m
find d , k
we can write this as

e.d - e.k - k.(m-e) =1

so d-k=X
k=y
so we have to find
eX - kY =1
and so on
keep reducing
till one of the terms becomes unity etc
and we are set

like 10 x - 21 y = 1
10x -10y -11y =1
10(x-y) -11 y =1
10X - 11Y=1
10(X-Y) -Y=1
y=-1 and X-Y=0 is one solution
and so on
so X=-1
so x-y = -1
so x=-2

@alokdube:

In the first post you state:

z=a^xy mod p=7^8 mod 11 = 9
z=a^xy mod p=7^28 mod 11 = 9
z=a^xy mod p =7^48 mod 11 = 9
z=a^xy mod p=7^168 mod 11 = 9

But this is trivially deduced from the theorem (derived from Fermat's Theorem) that:

When raising a number to a power mod p, the exponent can be reduced to it's least positive residue mod p-1

Thus in the above equations, as 8 = 28 = 48 = 168 mod 10, so 7^8 mod 11 must produce the same result as all the other similar expressions.

This has gone sooooo far over my head now I go cross eyed when I try to read it!