Math Is Fun Forum
You are not logged in.
- Topics: Active | Unanswered
Pages: 1
#1 Re: Help Me ! » need help with crypto system » 2009-04-06 20:43:40
This could be NP-hard problem, though there is some flexibility for this problem. I will write shortly the original problem I was trying to solve, which I hope will make more sense.
The original problem is as follows. Suppose I have several members in the room. I want to give to each of them different number.
So member Q[1] has some number, member Q[2] different number, etc.
Then I need to come up with public parameter P that I will announce in the room. Everybody is able to see that number, but only valid members Q[1], Q[2], Q[3] will be able to recover password
Q[1] mod P = Z (which is a secret number)
Q[2] mod P = Z
Q[3] mod P = Z
In case I want to exclude Q[3] member from the list, algorithm should be able to come up with different public parameter, let’s call it R that helps remaining members generate new secret number
Q[1] mod R = W (this is new secret)
Q[2] mod R = W
Obviously W != Z. since we cannot use old secret number.
Bruteforce password recovery could break this algorithm, but for simplicity we can assume this is not an issue.
#2 Re: Help Me ! » need help with crypto system » 2009-04-06 20:41:42
Thank you for your answers, I appreciate it. I hope I express myself below clear enough
Suppose I have sequence (array) Q with n elements, and they are all known. I need to find P and Z values (they are both unknown) that satisfy following condition
Q[1] mod P = Z
Q[2] mod P = Z
Q[3] mod P = Z
...
Q[n] mod P = Z
If any element of Q is excluded from sequence, e.g. Q[3], I was hoping to find another value R that satisfies following condition
Q[1] mod R = W
Q[2] mod R = W
...
Q[n] mod R = W
R and W are also unknown.
The CRT you suggested does partially address the problem.. We have integers n[1], n[2], ... , n[k] and a[1], a[2], ... , a[k]
x = a[1] mod n[1]
x = a[2] mod n[2]
the limitation with this problem is that all a values have to be same. Even if n values are same that works too.
(a[1] == a[2] == a[3] ... == a[k]) or (n[1] == n[2] == n[k])
#3 Re: Help Me ! » need help with crypto system » 2009-03-31 15:23:01
I apologize for such a messy description.
Integer- Member, I think you got the point.
So I’d like to find such P, that by dividing any element of Q, gives me same output - Z.
For example I have array size of 3.
Q[1] mod P = Z
Q[2] mod P = Z
Q[3] mod P = Z
And my question is, if I take out any of these elements (e.g. Q[3]), will I be able to find P’ that satisfies following condition
Q[1] mod P’ = W
Q[2] mod P’ = W
And obviously W != Z
I don’t really know if that is possible, but if there is such an algorithm, it’d be very helpful for one of my program.
Thanks guys for your answers, I greatly appreciate. there’s a good chance I’m asking for something that doesn’t have solution
#4 Re: Help Me ! » need help with crypto system » 2009-03-29 16:18:26
anybody?...
#5 Help Me ! » need help with crypto system » 2009-03-27 19:37:29
- linkin
- Replies: 8
Hi, first of all I must indicate I'm not math major, so my knowledge in math is limited
I was wondering, if there is any formula/operation by which I could do the following
I have number P and sequence Q[1,2,3...n]
If I apply some operation on P and any Q[i] could I get the same number for each i?
For example
P {some operation} Q[1] = Z
P {some operation} Q[2] = Z
and same thing applies to all i-th numbers in Q. will I be able to come up with such Z where only selected numbers e.g. Q[1], [5], [17] will be able to recover Z?
I hope I expressed myself clear enough 
any suggestion would be greatly appreciated. I already have looked into Broadcast Encryption, so if you guys have heard of something else, it'd be a great help
thanks in advance
Pages: 1