an observation
search for diffie hellman in the tips area this thread led to another that followed right through
Paul Dwyer
“In nature, it’s not the strongest nor the most intelligent who survives. It’s the most adaptable to change” - Charles Darwin
“If you can't explain it to a six-year old you really don't understand it yourself.” - Albert Einstein
“In nature, it’s not the strongest nor the most intelligent who survives. It’s the most adaptable to change” - Charles Darwin
“If you can't explain it to a six-year old you really don't understand it yourself.” - Albert Einstein
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.
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.
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 idlealokdube 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: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.
Good luck.In modular arithmetic exponentiation inverses (called discrete logarithms) are not easy to find!
What does this mean? A one-way function!
Re: an observation
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
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
Re: an observation
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
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
Re: an observation
@alokdube:
In the first post you state:
In the first post you state:
But this is trivially deduced from the theorem (derived from Fermat's Theorem) that: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
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.When raising a number to a power mod p, the exponent can be reduced to it's least positive residue mod p-1
Anthony Jordan
- Rook Zimbabwe
- Addict
- Posts: 4326
- Joined: Tue Jan 02, 2007 8:16 pm
- Location: Cypress TX
- Contact:
Re: an observation
This has gone sooooo far over my head now I go cross eyed when I try to read it!