Register to reply

RSA Algorithm Help

by James...
Tags: algorithm
Share this thread:
James...
#1
Jul10-09, 05:25 PM
P: 25
Struggling to put a number through this as I keep getting my original number as the encrypted number too.

A = 11
p = 3 q = 5
n = pq = 15
z = (p-1)(q-1) = 2*4 = 8
k = co-prime of z = 7

So,

A=11
n=15
z=8 (Public key)
k=7(Public key)

kj = 1 (mod z)
7j = 1 (mod 8)

for which I am getting j = 9/7 (private key)

Start of encryption...

A^k = E (mod n)
11^7 = E (mod 15)

19487171/15 = 1299144.733......

1299144 * 15 = 19487160

E = 19487171 - 19487160 = 11 (which is what I started with)


Tried using the decrypting part anyway and got....

E^j = A (mod n)

11^(9/7) = A (mod 15)

21.8239547419283/15 = 1.45493031612855

1 * 15 = 15

21.8239547419283 - 15 = 6.8239547419283 (which obviously isnt what I started with)

Any help where I am going wrong would be appreciated, I assume it is where mod is brought in as I havent used that function before 2 hours ago but it may be somewhere else.

Cheers
james
Phys.Org News Partner Mathematics news on Phys.org
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
Iranian is first woman to win 'Nobel Prize of maths' (Update)
Borek
#2
Jul10-09, 05:33 PM
Admin
Borek's Avatar
P: 23,533
Quote Quote by James... View Post
for which I am getting j = 9/7 (private key)
Shouldn't all number involved be integers?
James...
#3
Jul10-09, 05:38 PM
P: 25
I'm not sure. Thats where I think I have gone wrong though.

Think I messed up at

kj = 1 (mod z)
7j = 1 (mod 8)

trying to work out the private key as I have tried to teach myself how to do this from an example on a website without really knowing how to do it.

James

James...
#4
Jul12-09, 01:18 PM
P: 25
RSA Algorithm Help

Can anyone help with this? Will ask my math/physics teacher tomorrow but wouldnt mind having another go at it first.

Cheers
James
Borek
#5
Jul12-09, 01:45 PM
Admin
Borek's Avatar
P: 23,533
I am sure these should be all integers, but I have not played with RSA for several years.
James...
#6
Jul12-09, 02:25 PM
P: 25
I think you are right but I am getting fractions when the modulus function is introduced as I'm unsure how it works.

James
Borek
#7
Jul12-09, 03:12 PM
Admin
Borek's Avatar
P: 23,533
mod never gives fractions, mod is about finding remainder.

10 mod 3 = 1
12 mod 5 = 2

and so on.
HallsofIvy
#8
Jul12-09, 03:41 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,495
Quote Quote by James... View Post
I'm not sure. Thats where I think I have gone wrong though.

Think I messed up at

kj = 1 (mod z)
7j = 1 (mod 8)
Just try some possibilities: 7(1)= 7, 7(2)= 14= 8+ 6, 7(3)= 21= 2(8)+ 5, 7(4)= 28= 3(8)+ 4, 7(5)= 35= 4(8)+ 7, 7(6)= 42= 5(8)+ 2, 7(7)= 49= 6(8)+ 1. 7j= 1 (mod 8) if and only if u= 7 (mod 8). I can't speak for "kj= 1 (mod z)" because I don't know what z is!

trying to work out the private key as I have tried to teach myself how to do this from an example on a website without really knowing how to do it.

James


Register to reply

Related Discussions
Grover's Algorithm: is it really a search algorithm Quantum Physics 11
Help With Pseudo Coded Algorithm for The Diamond-Square Algorithm Engineering, Comp Sci, & Technology Homework 0
Algorithm homework Calculus & Beyond Homework 6
Develop the algorithm as a module Engineering, Comp Sci, & Technology Homework 5
A new algorithm? General Math 2