Fix rounding issue with FF1

2 files changed, 47 insertions, 13 deletions

diff --git a/crypto/src/crypto/fpe/SP80038G.cs b/crypto/src/crypto/fpe/SP80038G.cs
index 431fb119d..65dad0797 100644
--- a/crypto/src/crypto/fpe/SP80038G.cs
+++ b/crypto/src/crypto/fpe/SP80038G.cs
@@ -60,8 +60,8 @@ namespace Org.BouncyCastle.Crypto.Fpe
         private static ushort[] DecFF1(IBlockCipher cipher, int radix, byte[] T, int n, int u, int v, ushort[] A, ushort[] B)
         {
             int t = T.Length;
-            int b = ((int)Ceil(System.Math.Log((double)radix) * (double)v / LOG2) + 7) / 8;
-            int d = (((b + 3) / 4) * 4) + 4;
+            int b = CalculateB_FF1(radix, v);
+            int d = (b + 7) & ~3;
 
             byte[] P = CalculateP_FF1(radix, (byte)u, n, t);
 
@@ -161,8 +161,8 @@ namespace Org.BouncyCastle.Crypto.Fpe
         {
             int t = T.Length;
 
-            int b = ((int)Ceil(System.Math.Log((double)radix) * (double)v / LOG2) + 7) / 8;
-            int d = (((b + 3) / 4) * 4) + 4;
+            int b = CalculateB_FF1(radix, v);
+            int d = (b + 7) & ~3;
 
             byte[] P = CalculateP_FF1(radix, (byte)u, n, t);
 
@@ -237,6 +237,26 @@ namespace Org.BouncyCastle.Crypto.Fpe
             return EncryptFF3(cipher, radix, tweak64, buf, off, len);
         }
 
+        private static int CalculateB_FF1(int radix, int v)
+        {
+            //return (BigInteger.ValueOf(radix).Pow(v).Subtract(BigInteger.One).BitLength + 7) / 8;
+
+            int powersOfTwo = Integers.NumberOfTrailingZeros(radix);
+            int bits = powersOfTwo * v;
+
+            int oddPart = radix >> powersOfTwo;
+            if (oddPart != 1)
+            {
+                // Old version with rounding issues, especially for power of 2 radix, but maybe others.
+                //bits += (int)System.Math.Ceiling(System.Math.Log((double)oddPart) * (double)v / LOG2);
+
+                // Exact calculation, with possible performance issues if v is too large.
+                bits += BigInteger.ValueOf(oddPart).Pow(v).BitLength;
+            }
+
+            return (bits + 7) / 8;
+        }
+
         private static BigInteger[] CalculateModUV(BigInteger bigRadix, int u, int v)
         {
             BigInteger[] modUV = new BigInteger[2];
@@ -612,14 +632,5 @@ namespace Org.BouncyCastle.Crypto.Fpe
 
             return s;
         }
-
-	    private static int Ceil(double v)
-	    {
-		    int rv = (int)v;
-		    if ((double)rv < v)
-			    return rv + 1;
-
-            return rv;
-	    }
     }
 }
diff --git a/crypto/test/src/crypto/test/SP80038GTest.cs b/crypto/test/src/crypto/test/SP80038GTest.cs
index 7d2a76474..c1eac2a24 100644
--- a/crypto/test/src/crypto/test/SP80038GTest.cs
+++ b/crypto/test/src/crypto/test/SP80038GTest.cs
@@ -413,6 +413,28 @@ namespace Org.BouncyCastle.Crypto.Tests
             }
         }
 
+        private void ImplTestFF1Rounding()
+        {
+            int radix = 256;
+            byte[] key = Hex.DecodeStrict("000102030405060708090a0b0c0d0e0f");
+            byte[] tweak = Hex.DecodeStrict("0001020304050607");
+            byte[] asciiPT = Hex.DecodeStrict("000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738");
+            byte[] asciiCT = Hex.DecodeStrict("dc18bef8b7d23aa77d1daf7a50c2253c4bacb772129f70805ecd413775bc3bdf7927ce70f455dacf4fdf61b61ac73a5c90fd3d1759dca0bf27");
+            byte[] result = new byte[asciiPT.Length];
+
+            FpeEngine fpeEngine = new FpeFf1Engine();
+            FpeParameters fpeParameters = new FpeParameters(new KeyParameter(key), radix, tweak);
+
+            fpeEngine.Init(true, fpeParameters);
+            fpeEngine.ProcessBlock(asciiPT, 0, asciiPT.Length, result, 0);
+            IsTrue("Failed FF1 rounding test (encryption)", AreEqual(asciiCT, result));
+
+            fpeEngine.Init(false, fpeParameters);
+            fpeEngine.ProcessBlock(asciiCT, 0, asciiCT.Length, result, 0);
+
+            IsTrue("Failed FF1 rounding test (decryption)", AreEqual(asciiPT, result));
+        }
+
         private void ImplTestFF3_1Bounds()
         {
             string bigAlpha = "+-ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz";
@@ -505,6 +527,7 @@ namespace Org.BouncyCastle.Crypto.Tests
             ImplTestFF1();
             ImplTestFF1w();
             ImplTestFF1Bounds();
+            ImplTestFF1Rounding();
             ImplTestFF3_1();
             ImplTestFF3_1w();
             ImplTestFF3_1_255();