Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
ANS1 parser for a RSA PrivateKey. Can also create a private key from just a P and Q by calculating the D, DP, DQ, and InverseQ. Create real private keys from small primes for CTFs, factoring challenges or the lulz.
public class ANS1PrivateKey : IDisposable
{
public BigInteger Modulus = BigInteger.MinusOne;
public BigInteger Exponent = BigInteger.MinusOne;
public BigInteger P = BigInteger.MinusOne;
public BigInteger Q = BigInteger.MinusOne;
public BigInteger D = BigInteger.MinusOne;
public BigInteger DP = BigInteger.MinusOne;
public BigInteger DQ = BigInteger.MinusOne;
public BigInteger InverseQ = BigInteger.MinusOne;
public bool IsPrivateKey { get; private set; }
public RSAParameters RsaParameters;
private int byteCount;
private IEnumerable<byte> byteBuffer;
private static byte SequenceTag = 0x30; // ASN.1 tag for sequence
private static byte IntTag = 0x02; // ASN.1 tag for int; Length encoded on next byte
private static byte Version0 = 0x00; // Version 0; RSA private key with 2 primes
public ANS1PrivateKey(byte[] bytes)
{
byteCount = bytes.Length;
byteBuffer = bytes.ToList();
ParseBuffer();
}
public ANS1PrivateKey(RSAParameters key)
{
RSAParameters temp = new RSAParameters();
temp.Modulus = key.Modulus.ToArray();
temp.Exponent = key.Exponent.ToArray();
IsPrivateKey = !(key.D == null);
if (IsPrivateKey)
{
temp.P = key.P.ToArray();
temp.Q = key.Q.ToArray();
temp.D = key.D.ToArray();
temp.DP = key.DP.ToArray();
temp.DQ = key.DQ.ToArray();
temp.InverseQ = key.InverseQ.ToArray();
}
RsaParameters = temp;
this.Modulus = new BigInteger(SwapEndianness(temp.Modulus));
this.Exponent = new BigInteger(SwapEndianness(temp.Exponent));
if (IsPrivateKey)
{
this.P = new BigInteger(SwapEndianness(temp.P));
this.Q = new BigInteger(SwapEndianness(temp.Q));
this.D = new BigInteger(SwapEndianness(temp.D));
this.DP = new BigInteger(SwapEndianness(temp.DP));
this.DQ = new BigInteger(SwapEndianness(temp.DQ));
this.InverseQ = new BigInteger(SwapEndianness(temp.InverseQ));
}
}
public ANS1PrivateKey(BigInteger p, BigInteger q)
{
P = p;
Q = q;
Modulus = BigInteger.Multiply(P, Q);
Exponent = new BigInteger(65537);
IsPrivateKey = true;
BigInteger pMinusOne = (P - 1);
BigInteger qMinusOne = (Q - 1);
BigInteger phi = BigInteger.Multiply(pMinusOne, qMinusOne);
// Choose D such that:
// (D * Exponent) ≡ 1 (mod phi(N))
D = Maths.ModularMultiplicativeInverse(Exponent, phi);
DP = D.Mod(pMinusOne);
DQ = D.Mod(qMinusOne);
// Choose InverseQ such that:
// (InverseQ * Q) ≡ 1 (mod P)
InverseQ = Maths.ModularMultiplicativeInverse(Q, P);
}
public void Dispose()
{
byteCount = -1;
byteBuffer = null;
Modulus = Exponent = D = P = Q = DP = DQ = InverseQ = BigInteger.MinusOne;
}
public static void AssertValidRSAPrivateKey(RSAParameters key)
{
ANS1PrivateKey privateKey = new ANS1PrivateKey(key);
privateKey.AssertValidRSAPrivateKey();
}
public void AssertValidRSAPrivateKey()
{
BigInteger pMinusOne = (P - 1);
BigInteger qMinusOne = (Q - 1);
BigInteger phi = BigInteger.Multiply(pMinusOne, qMinusOne);
// Public key validity checks
Assert(Modulus == (P * Q), "Modulus ≠ P*Q");
Assert(1 == ((D * Exponent) % phi), "D*Exponent ≢ 1 (mod phi(N))"); // (d) (e) mod phi(n) = 1
Assert(DP == (D % pMinusOne), "DP ≢ D (mod P-1)");
Assert(DQ == (D % qMinusOne), "DQ ≢ D (mod Q-1)");
Assert(1 == ((InverseQ * Q) % P), "Q*Q¯¹ ≢ 1 (mod P)"); //(InverseQ)(q) = 1 mod p
}
private void ParseBuffer()
{
AssertNextValueIs(SequenceTag);
byte prefixLength = TakeBuffer();
BigInteger bodyLength = BytesToBigInteger(TakeBuffer(2));
int bufferLen = byteBuffer.Count();
if (!bodyLength.Equals(bufferLen))
{
ThrowFormatException(bodyLength, bufferLen);
}
AssertNextValueIs(IntTag);
AssertNextValueIs(0x01);
AssertNextValueIs(Version0);
Modulus = GetNextVariableValue();
Exponent = GetNextVariableValue();
IsPrivateKey = (byteBuffer.Count() > 2);
if (IsPrivateKey)
{
IsPrivateKey = true;
D = GetNextVariableValue();
P = GetNextVariableValue();
Q = GetNextVariableValue();
DP = GetNextVariableValue();
DQ = GetNextVariableValue();
InverseQ = GetNextVariableValue();
}
}
private BigInteger GetNextVariableValue()
{
AssertNextValueIs(IntTag);
int readSize = 0;
byte variableSize = TakeBuffer();
if (variableSize > 127)
{
int longFormSize = variableSize & (byte)127;
readSize = (int)ANS1PrivateKey.BytesToBigInteger(TakeBuffer(longFormSize));
}
else
{
readSize = variableSize;
}
byte peek = PeekBuffer();
if (peek.Equals(0x00))
{
TakeBuffer();
readSize--;
}
byte[] variableBytes = TakeBuffer(readSize);
BigInteger variableValue = BytesToBigInteger(variableBytes);
variableBytes = null;
return variableValue;
}
private byte PeekBuffer()
{
return byteBuffer.First();
}
private byte TakeBuffer()
{
return TakeBuffer(1).First();
}
private byte[] TakeBuffer(int count)
{
byte[] result = byteBuffer.Take(count).ToArray();
byteBuffer = byteBuffer.Skip(count);
return result;
}
private void AssertNextValueIs(byte value)
{
byte bufferValue = TakeBuffer();
if (!bufferValue.Equals(value))
{
ThrowFormatException(bufferValue, value);
}
}
private void AssertNextValueIs(byte[] value)
{
byte[] chunk = TakeBuffer(value.Length);
if (chunk.Length != value.Length)
{
ThrowFormatException(chunk.Length, value.Length);
}
int counter = 0;
foreach (byte bite in chunk)
{
if (!bite.Equals(value[counter]))
{
ThrowFormatException(bite, value[counter]);
}
counter++;
}
chunk = null;
}
private static byte[] SwapEndianness(byte[] input)
{
byte[] byteArray = input.ToArray();
if (byteArray.Last() == byte.MinValue)
{
byteArray = byteArray.Take(byteArray.Length - 1).ToArray();
}
Array.Reverse(byteArray);
if (byteArray[byteArray.Length - 1] > 127)
{
Array.Resize(ref byteArray, byteArray.Length + 1);
byteArray[byteArray.Length - 1] = 0;
}
return byteArray;
}
public static BigInteger BytesToBigInteger(byte[] input)
{
BigInteger total = new BigInteger(0);
if (input == null || input.Length == 0)
{
return total;
}
byte[] localCopy = new List<byte>(input).ToArray();
Array.Reverse(localCopy);
int counter = 0;
BigInteger digitValue = new BigInteger(0);
BigInteger placeValue = new BigInteger(0);
foreach (byte octet in localCopy)
{
placeValue = BigInteger.Pow(256, counter++);
digitValue = octet * placeValue;
total += digitValue;
}
return total;
}
private void ThrowFormatException(object expected = null, object actual = null)
{
Assert(expected == actual, $"Not a valid Version 0 (private key) ASN.1 sequence: Byte #{(byteCount - byteBuffer.Count())}: Expected value: {expected.ToString()}, Actual value: {actual.ToString()}.");
}
private static void Assert(bool condition, string messageOnAssertFail)
{
if (!condition)
{
throw new Exception(messageOnAssertFail);
}
}
public static string ToXMLDocument(ANS1PrivateKey key)
{
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.AppendLine($"<RSAKeyValue>");
stringBuilder.AppendLine($" <Modulus>{Convert.ToBase64String(SwapEndianness(key.Modulus.ToByteArray()))}</Modulus>");
stringBuilder.AppendLine($" <Exponent>{Convert.ToBase64String(SwapEndianness(key.Exponent.ToByteArray()))}</Exponent>");
if (key.IsPrivateKey)
{
stringBuilder.AppendLine($" <P>{Convert.ToBase64String(SwapEndianness(key.P.ToByteArray()))}</P>");
stringBuilder.AppendLine($" <Q>{Convert.ToBase64String(SwapEndianness(key.Q.ToByteArray()))}</Q>");
stringBuilder.AppendLine($" <DP>{Convert.ToBase64String(SwapEndianness(key.DP.ToByteArray()))}</DP>");
stringBuilder.AppendLine($" <DQ>{Convert.ToBase64String(SwapEndianness(key.DQ.ToByteArray()))}</DQ>");
stringBuilder.AppendLine($" <D>{Convert.ToBase64String(SwapEndianness(key.D.ToByteArray()))}</D>");
stringBuilder.AppendLine($" <InverseQ>{Convert.ToBase64String(SwapEndianness(key.InverseQ.ToByteArray()))}</InverseQ>");
}
stringBuilder.AppendLine($"</RSAKeyValue>");
stringBuilder.Append(Environment.NewLine);
return stringBuilder.ToString();
}
public override string ToString()
{
return ToXMLDocument(this);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment