package org.bouncycastle.pqc.math.ntru.util; import java.io.IOException; import java.io.InputStream; import java.math.BigInteger; import org.bouncycastle.util.Arrays; /** * Converts a coefficient array to a compact byte array and vice versa. */ public class ArrayEncoder { /** * Bit string to coefficient conversion table from P1363.1. Also found at * {@link http://stackoverflow.com/questions/1562548/how-to-make-a-message-into-a-polynomial} *
* Convert each three-bit quantity to two ternary coefficients as follows, and concatenate the resulting * ternary quantities to obtain [the output]. *
*
* {0, 0, 0} -> {0, 0}
*
* {0, 0, 1} -> {0, 1}
* {0, 1, 0} -> {0, -1}
* {0, 1, 1} -> {1, 0}
* {1, 0, 0} -> {1, 1}
* {1, 0, 1} -> {1, -1}
* {1, 1, 0} -> {-1, 0}
* {1, 1, 1} -> {-1, 1}
*
* Convert each set of two ternary coefficients to three bits as follows, and concatenate the resulting bit * quantities to obtain [the output]: *
*
* {-1, -1} -> set "fail" to 1 and set bit string to {1, 1, 1}
* {-1, 0} -> {1, 1, 0}
\
*
* {-1, 1} -> {1, 1, 1}
* {0, -1} -> {0, 1, 0}
* {0, 0} -> {0, 0, 0}
* {0, 1} -> {0, 0, 1}
* {1, -1} -> {1, 0, 1}
* {1, 0} -> {0, 1, 1}
* {1, 1} -> {1, 0, 0}
*
q
,
* to a byte array leaving no gaps between bits.q
must be a power of 2.
*
* @param a the input array
* @param q the modulus
* @return the encoded array
*/
public static byte[] encodeModQ(int[] a, int q)
{
int bitsPerCoeff = 31 - Integer.numberOfLeadingZeros(q);
int numBits = a.length * bitsPerCoeff;
int numBytes = (numBits + 7) / 8;
byte[] data = new byte[numBytes];
int bitIndex = 0;
int byteIndex = 0;
for (int i = 0; i < a.length; i++)
{
for (int j = 0; j < bitsPerCoeff; j++)
{
int currentBit = (a[i] >> j) & 1;
data[byteIndex] |= currentBit << bitIndex;
if (bitIndex == 7)
{
bitIndex = 0;
byteIndex++;
}
else
{
bitIndex++;
}
}
}
return data;
}
/**
* Decodes a byte
array encoded with {@link #encodeModQ(int[], int)} back to an int
array.N
is the number of coefficients. q
must be a power of 2
.N
coefficients between 0
and q-1
*/
public static int[] decodeModQ(byte[] data, int N, int q)
{
int[] coeffs = new int[N];
int bitsPerCoeff = 31 - Integer.numberOfLeadingZeros(q);
int numBits = N * bitsPerCoeff;
int coeffIndex = 0;
for (int bitIndex = 0; bitIndex < numBits; bitIndex++)
{
if (bitIndex > 0 && bitIndex % bitsPerCoeff == 0)
{
coeffIndex++;
}
int bit = getBit(data, bitIndex);
coeffs[coeffIndex] += bit << (bitIndex % bitsPerCoeff);
}
return coeffs;
}
/**
* Decodes data encoded with {@link #encodeModQ(int[], int)} back to an int
array.N
is the number of coefficients. q
must be a power of 2
.byte
array encoded with {@link #encodeMod3Sves(int[])} back to an int
array
* with N
coefficients between -1
and 1
.int
array whose elements are between -1
and 1
, to a byte array.
* coeffs[2*i]
and coeffs[2*i+1]
must not both equal -1 for any integer i
,
* so this method is only safe to use with arrays produced by {@link #decodeMod3Sves(byte[], int)}.int
array whose elements are between -1
and 1
, to a byte array.
*
* @return the encoded array
*/
public static byte[] encodeMod3Tight(int[] intArray)
{
BigInteger sum = BigInteger.ZERO;
for (int i = intArray.length - 1; i >= 0; i--)
{
sum = sum.multiply(BigInteger.valueOf(3));
sum = sum.add(BigInteger.valueOf(intArray[i] + 1));
}
int size = (BigInteger.valueOf(3).pow(intArray.length).bitLength() + 7) / 8;
byte[] arr = sum.toByteArray();
if (arr.length < size)
{
// pad with leading zeros so arr.length==size
byte[] arr2 = new byte[size];
System.arraycopy(arr, 0, arr2, size - arr.length, arr.length);
return arr2;
}
if (arr.length > size)
// drop sign bit
{
arr = Arrays.copyOfRange(arr, 1, arr.length);
}
return arr;
}
/**
* Converts a byte array produced by {@link #encodeMod3Tight(int[])} back to an int
array.
*
* @param b a byte array
* @param N number of coefficients
* @return the decoded array
*/
public static int[] decodeMod3Tight(byte[] b, int N)
{
BigInteger sum = new BigInteger(1, b);
int[] coeffs = new int[N];
for (int i = 0; i < N; i++)
{
coeffs[i] = sum.mod(BigInteger.valueOf(3)).intValue() - 1;
if (coeffs[i] > 1)
{
coeffs[i] -= 3;
}
sum = sum.divide(BigInteger.valueOf(3));
}
return coeffs;
}
/**
* Converts data produced by {@link #encodeMod3Tight(int[])} back to an int
array.
*
* @param is an input stream containing the data to decode
* @param N number of coefficients
* @return the decoded array
*/
public static int[] decodeMod3Tight(InputStream is, int N)
throws IOException
{
int size = (int)Math.ceil(N * Math.log(3) / Math.log(2) / 8);
byte[] arr = Util.readFullLength(is, size);
return decodeMod3Tight(arr, N);
}
private static int getBit(byte[] arr, int bitIndex)
{
int byteIndex = bitIndex / 8;
int arrElem = arr[byteIndex] & 0xFF;
return (arrElem >> (bitIndex % 8)) & 1;
}
}