need help with crypto system

linkin · 2009-03-27 19:37:29

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

linkin · 2009-03-29 16:18:26

anybody?...

Ricky · 2009-03-29 17:20:36

Perhaps I am not understanding the question. But without changing the operation this isn't possible. Let $ stand for any operation. Assume you can define $ such that P $ Q[0] = K and P $ Q[1] = L where K is not equal to L. Then if we set Q[0] = 0 and Q[1] = 1, then:

P $ Q[0] = K and so P $ 0 = K
P $ Q[1] = L and so P $ 1 = L

But now take a second Q, Q[0] = 1 and Q[1] = 0.

P $ Q[0] = K and so P $ 1 = K

But now we have P $ 1 = K and P $ 1 = L with K and L not being equal. This is not possible.

integer · 2009-03-30 01:10:26

Could you elaborate and give a small example of what you want to happen.

If your example were change:

Q[1] mod P = Z
Q[2] mod P = Z

This would work.

linkin · 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

integer · 2009-04-01 11:43:09

The Chinese Remaind Theorem (CRT) seems partially helpful.
The CRT typically has different moduli.

Could you give a specific example.
Exactly what numbers do you know, and what is unknown.

It looks as if all values of Q[] are known.
It appears as if you know what Z is and you are looking for P and P'

If that is the case:
subtract Z from each of the Q[], then perform a gcd operation on the group.

gcd( Q[1]-Z, Q[2]-Z, Q[3]-Z, Q[4]-Z, Q[5]-Z ) == P

I'm not sure that I understand the question.
Please elaborate with a couple small examples.

linkin · 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])

Last edited by linkin (2009-04-06 20:49:59)

linkin · 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.

integer · 2009-04-09 09:36:06

linkin wrote:

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, lets 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.

numbers(prime?) ,1111,1719,2643,4177,4379,4797,5431,7817,9741,3789,4513,8741,1917
ID,Q[], &residues
A,103872994,49,700,451,3535,3114,3553,5119,698,4711,1348,1786,3691,349
B,157971872,1004,929,2405,1909,3826,1865,[b]375[/b],5936,2075,884,3333,4520,1487
C,105879513,102,1146,933,[b]917[/b],4051,129,2168,6065,4584,3486,20,8521,1686
D,149575546,505,199,247,1353,2043,289,[b]375[/b],5068,2491,982,1187,8295,1621
E,190090806,928,348,960,3890,2795,87,[b]375[/b],4817,4932,465,3246,279,1086
F,146230050,230,1596,789,1634,2103,3099,[b]375[/b],5248,7899,1173,4337,1861,1290
G,131537022,177,861,198,3292,620,3282,3633,363,4299,1887,1124,2454,150
H,108196757,911,1178,266,4103,425,422,[b]375[/b],1660,3470,1862,2095,659,1277
I,156049460,622,359,1454,[b]917[/b],3795,3050,537,6506,8381,3284,3459,5128,1826
J,159203095,128,1348,1990,[b]917[/b],171,259,4192,2073,5932,682,2507,3262,79
K,157757853,297,66,2469,[b]917[/b],4378,3711,3596,2976,2358,2838,1425,285,255
L,197629034,1021,761,1352,2633,385,2228,375,7457,3626,2372,251,3765,1670

You specifiy a number for the entire group.
In this sample only two primes will produce the desired keys.
The secret keys are 917 and 375.

Is this what you are attempting?

This generation of number is very easy to do.
Trying different primes will require a lot of effort and my be effective enough to preclude being broken by that method.

HOWEVER, it is easily broken, NOT by trying different primes.

The Q[] numbers are only a few thousand times larger than the modulus.
Thus this is easily cracked by differences of the Q[] and residues.

If possible create a set of Q[] values, that you want to use and show them here.

Math Is Fun Forum

#1 2009-03-27 19:37:29

need help with crypto system

#2 2009-03-29 16:18:26

Re: need help with crypto system

#3 2009-03-29 17:20:36

Re: need help with crypto system

#4 2009-03-30 01:10:26

Re: need help with crypto system

#5 2009-03-31 15:23:01

Re: need help with crypto system

#6 2009-04-01 11:43:09

Re: need help with crypto system

#7 2009-04-06 20:41:42

Re: need help with crypto system

#8 2009-04-06 20:43:40

Re: need help with crypto system

#9 2009-04-09 09:36:06

Re: need help with crypto system

Board footer