Algorithms



I'm trying to code the Secure Remote Password protocol (RFC 2945). I wasn't sure if I was getting the correct values at each stage so I did some searching and came across RFC 5054 which supplies some test vectors. I believe my problem is coming from the conversions between hex string, integers, bytes, and BigIntegers, however I just can't seem to track it down. Below is just one parameter that I need to calculate, but since all the other parameters are calculated in a similar way, if I can get this one working, all the rest should be fine.
Parameters
N  Large 1,024 bit safe prime number. The hex value is:
EEAF0AB9 ADB38DD6 9C33F80A FA8FC5E8 60726187 75FF3C0B 9EA2314C
9C256576 D674DF74 96EA81D3 383B4813 D692C6E0 E0D5D8E2 50B98BE4
8E495C1D 6089DAD1 5DC7D7B4 6154D6B6 CE8EF4AD 69B15D49 82559B29
7BCF1885 C529F566 660E57EC 68EDBC3C 05726CC0 2FD4CBF4 976EAA9A
FD5138FE 8376435B 9FC61D2F C0EB06E3
g  A generator of N with a value of 2
a  Private random number. Test vector provides the following to use:
60975527 035CF2AD 1989806F 0407210B C81EDC04 E2762A56 AFD529DD
DA2D4393
A  Public value I'm trying to computer. A = g^a % N
Obviously these are large numbers to be working with, so I'm using the BigInteger class from the System.Numeric namespace in VB.NET 4. I'm tried many different ways to get this to work. Below is my latest incarnation of the code trying to compute A:
Dim strN As String = "EEAF0AB9ADB38DD69C33F80AFA8FC5E86072618775FF3C0B9EA2314C" & _
"9C256576D674DF7496EA81D3383B4813D692C6E0E0D5D8E250B98BE4" & _
"8E495C1D6089DAD15DC7D7B46154D6B6CE8EF4AD69B15D4982559B29" & _
"7BCF1885C529F566660E57EC68EDBC3C05726CC02FD4CBF4976EAA9A" & _
"FD5138FE8376435B9FC61D2FC0EB06E3"
Dim N As BigInteger = BigInteger.Parse(strN, Globalization.NumberStyles.HexNumber)
Dim g As New BigInteger(2)
Dim private_a_hex As String = "60975527035CF2AD1989806F0407210BC81EDC04E2762A56AFD529DDDA2D4393"
Dim private_a As BigInteger = BigInteger.Parse(private_a_hex, Globalization.NumberStyles.HexNumber)
Dim public_A As BigInteger = BigInteger.ModPow(g, private_a, N)
Dim public_A_hex As String = public_A.ToString("X")
When I run the above code public_A_hex (which is hold the value of A), I'm getting the following hex string:
0CB3B3D1 59B9DFD8 7D5995E2 BAF4D4DC E8A27402 B388652E 133E4A67
2D63FAE8 D432E166 2C2A23A3 8E67D164 49282934 20AC0693 7F3182F5
3EB21DA2 5CE20CCB 27075CCB 21664335 9CFB2816 7B378F9A F0F9534F
6A2BB9E8 9A5FEAD2 38DFDF7C ABDB747B FEB127CB 9E4A08DF 08D813F5
D874B65B 9D43AAAD 102700BC 160365F7
However RFC 5054 says that A should be the follow:
61D5E490 F6F1B795 47B0704C 436F523D D0E560F0 C64115BB 72557EC4
4352E890 3211C046 92272D8B 2D1A5358 A2CF1B6E 0BFCF99F 921530EC
8E393561 79EAE45E 42BA92AE ACED8251 71E1E8B9 AF6D9C03 E1327F44
BE087EF0 6530E69F 66615261 EEF54073 CA11CF58 58F0EDFD FE15EFEA
B349EF5D 76988A36 72FAC47B 0769447B
I'm thinking the error is coming from the endianness of the byte arrays/hex strings; I've tried reversing arrays before and after each conversion with still no luck. I don't know where to go from here at this point as I've been working on this for a little over 2 days.
I know that there are some libraries out there, but at this point I don't want to use them. Since the values don't work out, and I can't figure out why, I would like to know what I'm doing wrong and improve my knowledge in the process.
Any help or guidance would be greatly appreciated.
Thanks,
Dominick





There's a problem there. The number
EEAF0AB9 ADB38DD6 9C33F80A FA8FC5E8 60726187 75FF3C0B 9EA2314C
9C256576 D674DF74 96EA81D3 383B4813 D692C6E0 E0D5D8E2 50B98BE4
8E495C1D 6089DAD1 5DC7D7B4 6154D6B6 CE8EF4AD 69B15D49 82559B29
7BCF1885 C529F566 660E57EC 68EDBC3C 05726CC0 2FD4CBF4 976EAA9A
FD5138FE 8376435B 9FC61D2F C0EB06E3
as interpreted with E3 being the lowest byte and EE the highest, is not a prime number. It's divisible by 2609.
That same number interpreted as EE being the low byte and 3E the high byte (ie the stringreverse), is not an prime either, rather trivially, since E is even.
I have tried other arrangements, but I have yet to find one that's actually prime.
Chances are that the other numbers are using some weird order as well.





Thanks for the responese however, after burning through the night and checking the code hundreds of time, I found the issue. It turned out that the number was being interpreted as a negative number by the BigInteger class. Once I added a 0 to the beginning of the prime number the code worked and matched up with all the test vector's outputs.





Makes sense, I should probably have thought of that







General News Suggestion Question Bug Answer Joke Rant Admin
Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.