Omnimaga
Calculator Community => TI Calculators => Axe => Topic started by: Freyaday on April 20, 2011, 11:01:26 am
-
I'm trying to create an implementation of SHA-2 on calc, but I'm having trouble figuring out the diagram on Wikipedia. Specifically, I have no idea what it means by carry-free addition. Isn't that just xor in binary? And what, exactly, are R and W and where do they come from?
-
Yes, Carry-free addition is just the Xor operation (for 1 bit numbers only!). However, if you just want the cryptography, may I recommend SHA-1 (http://www.unitedti.org/forum/index.php?showtopic=9582)? If you want to learn, then I'd recommend trying a simpler, more widely used hash function like MD5.
PS: SHA-2 defines more than one function :)
-
Yes, Carry-free addition is just the Xor operation (for 1 bit numbers only!). However, if you just want the cryptography, may I recommend SHA-1 (http://www.unitedti.org/forum/index.php?showtopic=9582)? If you want to learn, then I'd recommend trying a simpler, more widely used hash function like MD5.
PS: SHA-2 defines more than one function :)
MD5 is indeed simpler and easier to make.
-
I don't do easy.
SHA-2 is probably gonna be the standard by the time I graduate from college.
http://ourl.ca/10538
So. What are these other functions?
-
Freyaday, unless you're graduating from college in the next four years, the SHA-3 algorithm will almost certainly be the standard. Just saying.
Anyway, I'll post an explanation of SHA-2 later. Time to go...
-
I know. But the competition to create SHA-3 hasn't even happened yet, and companies are probably gonna stick with SHA-2 except for their most highly sensitive stuffs.
-
I know. But the competition to create SHA-3 hasn't even happened yet, and companies are probably gonna stick with SHA-2 except for their most highly sensitive stuffs.
SHA-3 is not gonna be created so soon, I guess.
What language are you used to create this SHA thing? Axe?
-
Axe.
-
The only reason I can think of to make SHA-3 is if they found a flaw in sha-2.
Also, they'll be really similar.
-
I know. But the competition to create SHA-3 hasn't even happened yet, and companies are probably gonna stick with SHA-2 except for their most highly sensitive stuffs.
Um, the competition started almost three years ago (http://csrc.nist.gov/groups/ST/hash/sha-3/index.html). Also, companies will start replacing their SHA-2 algorithms within a few years, hence the "4 years" thing I mentioned in my previous post. But, I'll assume you have some legitimate use for SHA-2, since I likewise expect people to understand my use of Hex rather than ASM or C.
Okay, first off, there are a few kinds of SHA-2 algorithms. The most common are probably SHA-224 and SHA-256, since these are the versions endorsed by NIST. I'll focus on the SHA-224 algorithm for no particular reason. The two algorithms are precisely identical except for the initial state of the function and the ending truncation of the hash.
Before we start, I'm going to tell you that you will have to write routines for *every* arithmetic operation you do in with a SHA-algorithm. They are really much more suited to Assembly than Axe, as they only work when the word size is 32 bits, something that Axe doesn't natively permit. Also, addition is always taken modulo 232. Then, you also have to work out how you're going to do right shifts (SHR), which are something very easily done inASM. This is actually very simple. All you have to do is divide the number by two for each single shift right. However, for the upper 16 bits of each number, you will have to check each bit position to see if you should set the corresponding bit position in the lower 16 bits. Once you have an arithmetic shift, you also need the rotate right and left operations, which are synthesized for n bit rotations as follows:
ROTR: (x >> n) v (x << 32 - n)
ROTL: (x << n) ^ (x >> 32 - n)
Note that ROTRN=ROTL32-N
Also, SHA-256 employs six functions to compute the hash:
Ch( x, y, z) = ( x ^ y) XOR (NOT(x) ^ z)
Maj( x, y, z) = ( x ^ y) XOR ( x ^ z) XOR( y ^ z)
∑0 = ROTR2 XOR ROTR13 XOR ROTR22
∑1 = ROTR6 XOR ROTR11 XOR ROTR25
σ0 = ROTR7 XOR ROTR18 XOR SHR3
σ0 = ROTR17 XOR ROTR19 XOR SHR10
To begin with, the SHA-224 standard defines eight constants for the initial state. These are
H0 = c1059ed8
H1 = 367cd507
H2 = 3070dd17
H3 = f70e5939
H4 = ffc00b31
H5 = 68581511
H6 = 64f98fa7
H7 = befa4fa4
Er, sorry, I apparently really need to be somewhere else right now. I'll try to finish when I get back. This should be enough material to understand the scope of the project and begin implementing it.
Willrandship: The reason is probably that it's now within reason to brute force SHA-2 hashes, whereas it wasn't back when it was implemented. Also, the SHA-3 standard will in all likelihood have nothing to do with the SHA-1 and SHA-2 hashes.
-
Can't you just make it a 4096-bit key, or higher? Since the brute force tech is the same type of tech used in decryption, it's easy to keep ahead of the brute forcers by using higher keys, since you can get the same fancier computer they have. It still remains out of their reach to decrypt.
What about having an algorithm that changes every X months? It would switch to a random semiprime, more often than the decryption time takes. That way, even if someone did factor your semiprime, by the time they did, you're on a different number!
Edit: By Technology, I was referring to faster, better hardware, not the software algorithms.
-
I got 32 bit addition figured out. Here's the carry:
.A: up 16 int 1
.B: low 16 int 1
.C: up 16 int 2
.D: low 16 int 2
If -B<=D
A+1->A
End
-
Fun. Now you can duplicate the concept for even higher bit counts, right?
-
Yeah. This is my bit rotation right.
A/2->C
B/2->D
If A^2
D+ e^(15)->D
End
If B^2
C+e^(15)->C
End
C->A
D->B
-
Yeah. This is my bit rotation right.
A/2->C
B/2->D
If A^2
D+ e^(15)->D
End
If B^2
C+e^(15)->C
End
C->A
D->B
If this is being done In pure axe, here is a better way to bit shift variable A one way right:
A^2 -> B
A/2 -> A
-2 * B + A -> A
And for bit rotation left: (for that first line, just forgot what 65536/2 is :P
A/(65536/2) -> B
A*2 +B -> A
;)
-
Ashbad, that's wonderful advice...except we're dealing with 32bit ints here, not 16. Sorry. Thanks for the tip, though!
Also, because Axe recognizes constants, I don't think it really matters how you represent 2^15.
-
Well, for 32 bits, its only a little bit more complex -- basically, you chain the shifts :) the carry of one isn't added to that word, but the next one, and then the second word's carry is added to the first. Here is what I mean, in the form of a modified right shift:
A^2 -> F
A/2 -> A
B^2 -> G
B/2 + (2**15 * F) -> B
A + (2**15 * G) -> A
As you can see, when you extend the bit number in most operations, you just have to split them into different word groupings and chain them to together :)
EDIT: I just had to change the bits to inverse then add :)
-
Ashbad, umm, I don't think that's gonna work.