prop2 instruction request "mod of sqr"

mctrivia

chip would it be possible to get an instruction that did the following equation?



it would be helpful for encryption. if M is the product of 2 primes then using the LSB of each iteration will give you a cryptographically strong random number generator.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board coming soon. $21.99 has backlight driver and touch sensitive decoder.

Phil Pilgrim (PhiPi)

Is 32 bits enough to be cryptographically strong these days?

-Phil

mctrivia

Depends on how much you have to encrypt. It is a streem encryption and only 1 bit is used. 32 bit is still good for 1mb or so.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board coming soon. $21.99 has backlight driver and touch sensitive decoder.

mctrivia

not sure if it would be possible because at the very least you need to square a 32bit number resulting in a 64 bit number then take the mod of that number and a 32 bit product of 2 primes. For small file transfers this is safe as long as a hacker can not figure out what the 2 primes used where. if they can figure out both primes then you are hooped.

What makes this encryption system so nice is:

1) can generate 1 bit at a time for streaming data
2) can be used as public/private key encryption
3) is secure as long as attaker does not know the primes used
4) can resume part way through a set of random values.

4 is important. if you are streaming encrypted data and some how the counters of the 2 devices get out of sync all data will become meaningless. a hash check can detect the error and the 2 devices can re sync by sending what step number they are on. sending the value of xn would be unsafe since it gives insight into the value of M used but sending the value of n does not give insight into the value of M. the value of xn can be computed by using the following but only if you know both primes.



▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board coming soon. $21.99 has backlight driver and touch sensitive decoder.

Sapieha

Hi mctrivia


Can You post LINK to this thread in my thread

Ideas for Chip

Ps that we have that good ideas in one place

Regards

Christoffer

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Nothing is impossible, there are only different degrees of difficulty.
For every stupid question there is at least one intelligent answer.
Don't guess - ask instead.
If you don't ask you won't know.
If your gonna construct something, make it·as simple as·possible yet as versatile as posible.


Sapieha

cgracey

mctrivia said...
chip would it be possible to get an instruction that did the following equation?



it would be helpful for encryption. if M is the product of 2 primes then using the LSB of each iteration will give you a cryptographically strong random number generator.

Okay, it looks like you need to square a number in a register, divide it by a some other value, and return a modulus to that register. So, you need some setup to define the mod divisor. The squaring is straightforward, though the division is going to take either a lot of hardware or some time. This could be done, but it would be a lot of transistors. The divide would only be viable if it happened over multiple clocks. And this divider probably needs to divide 64 bits into 32 bits, right? The idea sounds really neat.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔


Chip Gracey
Parallax, Inc.

Ale

Adding division of any kind would be very useful, even if it is multi-cycle or done in slices like the SuperH's. The rest could be done with 2 other instructions. MUL is already there.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Visit some of my articles at Propeller Wiki:
MATH on the propeller propeller.wikispaces.com/MATH
pPropQL: propeller.wikispaces.com/pPropQL
pPropQL020: propeller.wikispaces.com/pPropQL020
OMU for the pPropQL/020 propeller.wikispaces.com/OMU

mctrivia

yep x and m are both 32 bit so x sqrd will be 64bit. m will be the same value for the life of the encrypted stream so you could hard code the address for it making x the only address you really need. ideally the carry flag would be set to the least significant bit of the resulting x to allow for easy rolling into a long since for encryption only 1 bit of each iteration is used.

time/transistors. obviously faster would be nice but i will take as many cycles as i need to wait.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board now in. $21.99 has backlight driver and touch sensitive decoder.

Post Edited (mctrivia) : 12/2/2009 9:44:56 AM GMT

Phil Pilgrim (PhiPi)

A 32 x 32 = 64 single-cycle multiply (or two: 32 * 32 = 32L and 32 ** 32 = 32H single-cycle multiplies), and a 64 / 32 = 32Q:32R single-cycle division increment (especially if there was a REPEAT instruction to go with it) would be very helpful, Chip. Beyond that, though, things start to get very CISCy. I'm not sure how you'd specify the register pairs, though. Maybe require destination to be an even number. Then the LSB of the destination address could be used for something else, like specifying * vs. /.

-Phil

mctrivia

Those instructions would do but would mean 5 instructions per bit which would make an unrolled loop unattainable.

Mul x,x
Mod x,m
Mov y,x
Ror y,#1
Rolc r,#1

Instead of
Ssb x,m
Rolc r,#1

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board now in. $21.99 has backlight driver and touch sensitive decoder.

Phil Pilgrim (PhiPi)

Frankly, I think either of our wishes is going to be difficult, given the planned pipeline sequence and four-port RAM. It would take an extra pipeline step or two to read/write a dual register and, possibly, a five-port RAM, assuming single-cycle execution is still the goal.

-Phil

mctrivia

I would be happy with several cycles though the less the better.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
24 bit LCD Breakout Board now in. $21.99 has backlight driver and touch sensitive decoder.

BradC

Ale said...
MUL is already there.

I'd vote for a MAC instruction (preferably with a bigger accumulator, but I could live with 32 bit).

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
If you always do what you always did, you always get what you always got.

Phil Pilgrim (PhiPi)

I remember reading somewhere that a MAC was in the picture. It's great for doing DSP functions, although it's helpful if the radix point is somewhere in the middle and not after bit 0.

-Phil