How do you handle numbers larger than 32 bits?
Don M
Posts: 1,652
Take this equation for example:
This is 88^7. On my calculator the answer is 40,867,559,636,992 which is a 46 bit number. The above equation on the Propeller produces an answer of 945,815,552.
So is it possible and if so how do you do handle large numbers with the Propeller?
Sorry for my ignorance in this area....
Thanks.
Don
x := 88
y := 7
z := x
repeat y - 1
z := z * x
This is 88^7. On my calculator the answer is 40,867,559,636,992 which is a 46 bit number. The above equation on the Propeller produces an answer of 945,815,552.
So is it possible and if so how do you do handle large numbers with the Propeller?
Sorry for my ignorance in this area....
Thanks.
Don
Comments
So for bigger numbers, doubling whatever the the actual bit count that is available is done by using two registers .. one represents the low range and the other the high. And this is why the carry bit is included.
This 'double precision' operations for add, substract, multiply, and divide are pretty well standardized. But there are separate cases -- unsigned 32bit integers, signed 32bit integer, 32bit floating-point.
Be careful with what you read. These three -- double precision unsigned integer; double precision signed integer; and double precision floating point are often not clearly separated in discussion.
You have to get down to specific cases in each context for addition, subtraction, multiplication, and division.
If you want to explore what the 32bit registers are doing in a real context, using Forth on the Propeller to create each kind of double precision in the various operations will reveal a lot. I'd prefer to use Dave Hein's pfth for this as it conforms to the ANSI standards.
A word of caution -- floating point gets off into a world of its own. Microcontrollers operate much faster and more cleanly with signed or unsigned integers. IOW, floating point is really a conversion for human consumption.
As far as Spin goes, I don't know if there are any 64 bit objects in the Obex. F32 handles 32 bit floating point. I have a 64 bit floating point object that I wrote for C use (while debugging the propgcc 64 bit doubles). I've attached it to this message. There aren't any Spin interfaces yet, but the C interfaces are all contained in comments at the end of the PASM, so it wouldn't be too hard for someone who knows C and Spin to create a Spin interface.
Looking back, I now see that 'double precision' usually refers to only floating point. "Long long" is a more informal term that may not help with searching for tutorials. Most of the tutorials were written when processors used 8 or 16bits -- doubling the bit range was a more pressing need. So older books might provide a better presentation.
Signed integer is usually two's compliment format these days, even though in earlier times a lot of other solutions were explored. The most significant bit indicates sign, so the effective range is 31bits of numbers to both the positive and negative.
Unsigned integers are the easiest to explore, so likely the best place to start. You just have to account for every number being tied to a pair of 32bit registers.
I had this feeling already this morning that this was going to be your next question.
If someone is messing with modulus and exponentials it look like they are wanting to make some crypto algorithm. In the modern crypto world these numbers can get very big.
So, before anyone can advise, the questions are: What actually are you wanting to do? How big a number do you need to deal with?
There's some PASM code for working with 64-bits in the Propeller Wiki.
There's also floating point math but if you think you need floating point, you don't understand the problem.
Then you have to resort to "bignum" arithmetic. At it's simplest that is doing good old fashioned primary school time arithmetic, add, subtract, multiply, divide, the long hand way. Except instead of working decimal digits you are working with arrays 32 bit of binary chunks.
A quick way to multiply really big numbers is to take the Fourier transform of the "digits", then add them together, then take the Inverse Fourier Transform of the result.
I'm not sure Don M wants to get into that.
[SIZE=1][FONT=courier new]VAR long x, y OBJ pst : "parallax serial terminal" PUB tryDoublePrecision repeat pst.str(string(cr,"enter x: ")) ' can be positive or negative x := pst.decIn pst.str(string(cr,"enter y: ")) y := pst.decIn pst.str(string(cr,"answer z= $ ")) pst.hex(x ** y, 8) ' high 32 bits, msb is now the sign pst.hex(x * y, 8) ' append low 32 bits, shown as hex pst.newline [/FONT][/SIZE]If you want to show it in decimal instead of hex, you have to write a double precision routine to do that. You can find some useful unsigned double integer x*y/z routines in PhiPi's uMath object, http://obex.parallax.com/object/632.
It does get more complicated when you want to continue on as in your original question, where a number already double precision needs to be multiplied again times a single precision number. Then the product is going to have cross terms.
Yes you are correct. I'm not smart enough to know all that is needed to know and if I'm even asking the right questions.
I am trying to implement RSA encryption on the Propeller. I was hoping there might be some bits and pieces of objects that I could roll together and make this work.
For some background here I am working on a project that will involve sending an encrypted message to and from the Propeller. I was asked if it could do RSA with a 2048 bit or 1024 bit key. Not being bright enough about the relationship of what is required to do this to the capabilities of the Propeller I end up looking at bits and pieces of what I can find on the internet and try to make it work with what I know on the Propeller and end up asking a lot of questions here. I'm running into a lot of road blocks.
How big a number you ask? Well its beginning to look like a huge number but I don't really know.
Can the Propeller even do this? I haven't a clue. I see other discussions out on the internet about PIC chips doing RSA but not with a very large key and it is slow.
If someone would tell me I'm wasting my time then I'll move on to find some other solution. I think I'm in way over my head.... but I'm learning along the way.
How does a PC do these 2048 bit encryptions? The processors in them are only 32 or 64 bit. Dedicated math co-processor? Lots of memory? I don't know. Heck you can even create a key on-line through the internet. How does all this work?
Do I need floating point? I don't think so but I don't really know....
As you can tell I'm rather frustrated with all this at the moment....
In the beginning it looked like it was something that could be done. "Take this string of characters (key)- run it though this equation and get the answer." Looked innocent enough at first but now it isn't.
Shoot me...
Whoa, I just might give you a little "beat yourself silly much" talking to but not shoot.
Assuming that point A (the sender of said encrypted message) and point B the propeller gadget receiving the message are not on the same physically secure network, also assuming you want to use "standard" protocols and hence standard tools/software to talk to the gadget I would use one of these:
http://www.lantronix.com/device-networking/embedded-device-servers/xpico.html
Or similar and be done with it. Full IP/Stack, 256 AES, Web server, 384K storage and it's smaller than a micro SD sans ethernet jack.
The realities of the need for encryption are that files and documents are going to be exchanged on the world-wide web and need the protection.
So it seems that a Propeller-to-Propeller RSA encryption project is mostly academic. You already have the privacy and security of NOT being connected to the outside world.
I love the Propeller for what it is... a microcontroller with 8 processors.
It really was never intended to take on the role that a microcomputer plays in our daily life which includes word processing, handling email, browsing the web, and transferring encrypted documents over the internet.
In other words, I am beginning to suspect that the actual scale of real-world RSA encryption might be too much for the Propeller. You may be able to do something with a smaller sized key, but it won't be that secure and will mainly be an academic demonstration. (Which can be a worthy goal.)
So, I can't seem to grasp why a stand-alone RSA encryption scheme might be useful on a Propeller 1, unless it is actually connected to the internet.
How secure does this application need to be? Does it really need that 2k key? Remember that your scheme is more likely to be broken by the way you implement it than the the weakness of the key.
I suggest you Google around for the TEA encryption algorithm, http://en.wikipedia.org/wiki/Tiny_Encryption_Algorithm
and http://en.wikipedia.org/wiki/XTEA
These are much smaller, simpler, faster algorithms hat don't need the huge number arithmetic. They look pretty easy to do in assembler.
Here is a like to an implementation of the Blowfish algorithm for the Propeller. http://forums.parallax.com/showthread.php/101817-Here-s-Blowfish-(I-don-t-know-where-Hootie-is)
There are C libraries around to do RSA encryption -- for example the BigDigits multiiple-precision library.
Beware that there is much much more to encryption than just getting the RSA algorithm right. There are so many other important issues -- key generation and management, key distribution, random number generation (getting good cryptographic quality random numbers is hard!), etc. I suggest getting a copy of "Applied Cryptography" by Bruce Schneier and taking a look through it.
0) Have a huge pile of random numbers. Known to both to both ends of the link. The "Pad".
2) To send a message simply XOR the bytes of the message we the same number of bytes from the Pad.
3) For the next message use the next bytes from the Pad. Never use the same bytes twice!
4) And so on.
5) When you send a message, XORed as above, include with it the offset into the Pad of the bytes used to encrypt it. In this way the receiver can look up the same bytes in his copy of the pad and XOR the received message to get the plain text back.
6) If the same message has to be sent again, due to communication error or whatever, DO NOT use the same bytes from the PAD. Take some more.
Very easy and very quick.
Let's put the Pad on an SD card attached to the Propeller. Now with 8GB or random numbers on the Pad and 128 byte long messages we can send 64 million messages before the Pad is all used up! About 2 years at one message per second.
Where do we get 8GB or random numbers from? Use a propeller and the "Real Random" object perhaps.
Heater- This sounds easy and effective. The 2 "entities" that are communicating will always be the same. The server that the phone connects to via the wireless network and the Prop. I'll certainly entertain this idea.
http://en.wikipedia.org/wiki/One-time_pad
Yes, this is unbreakable if used correctly. Note the caveat, though! As you pointed out, you can never re-use random bytes from the pad. Also, the pad must be kept secure (nobody but sender and receiver can have copies), and the numbers have to be truly random. That last one is where many users of one time pads fall down. Generating secure random numbers is actually pretty hard, Even many hardware random number generators can have subtle biases. And under *no* circumstances can you use a software "random" (really pseudo-random) generator for a one time pad -- doing so makes it very weak indeed.
The pad is the "key". Keys have to be secured in a symmetric crypto system anyway.
Generating all those random number might be an issue. How fast can we get randomness from some hardware gadget? Even just writing 8GB of data to an SD card is a slow process. Might not be what you want to do if you have thousands of units to deal with.
If you do have thousands of units to deal with then you need to keep thousands of times 8GB somewhere !
All in all I would go for TEA or XTEA (isn't there now an XXTEA ?) on the Propeller.
Or give up and use a device to do it for you. Add a Raspberry Pi to the project and have that communicate using HTTPS or TLS.
So I have to ask if you are already gonna dangel a bluetooth device off of the prop to talk from a cell phone why not use one of the pico-x wifi modules with 256 AES. I mean are you guarding critical infrastructure? It would be neat to see one-time pad in OBEX but I tend to push past the "do it all myself" (unless cost per unit is the most driving factor) and finish the project. Caveot: unless this is hobby grade and not commercial grade, then by all means implement one-time pad, sounds challenging and fun. I would use GUIDs from different devices, then salt these with random numbers, then MD5 the results and chop or trim (randomly) to pad length. Whoops there goes my encryption security!