#define GOO_TEST #include #include "goo.c" #define GOO_ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) static const unsigned char GOO_AOL1_HASH[32] = { 0x7b, 0xd0, 0x82, 0x42, 0x7f, 0xf1, 0x8b, 0x35, 0xc8, 0xe2, 0xcd, 0xb2, 0xb8, 0x48, 0xd9, 0xc1, 0x39, 0x87, 0x7a, 0x27, 0x36, 0x63, 0xd1, 0xee, 0xea, 0x1d, 0x2a, 0x3d, 0x72, 0xb0, 0x11, 0x40 }; static const unsigned char GOO_AOL2_HASH[32] = { 0x1c, 0x25, 0xb6, 0xb4, 0xa8, 0xe3, 0xb6, 0x84, 0xdc, 0x82, 0x8c, 0x09, 0x22, 0xb2, 0x35, 0x93, 0x99, 0xc3, 0x6b, 0x93, 0xf3, 0xeb, 0xaa, 0x6b, 0x71, 0xa1, 0xe4, 0x12, 0x55, 0x55, 0x45, 0xba }; static const unsigned char GOO_RSA2048_HASH[32] = { 0x6a, 0xe9, 0xd0, 0x33, 0xc1, 0xd7, 0x6c, 0x4f, 0x53, 0x5b, 0x5a, 0xd5, 0xc0, 0x07, 0x39, 0x33, 0xa0, 0xb3, 0x75, 0xb4, 0x12, 0x0a, 0x75, 0xfb, 0xb6, 0x6b, 0xe8, 0x14, 0xea, 0xb1, 0xa9, 0xce }; static const unsigned char GOO_RSA617_HASH[32] = { 0x8a, 0x09, 0x0b, 0xf2, 0xcd, 0xbf, 0x9f, 0xac, 0x32, 0x1b, 0x2f, 0xfb, 0x48, 0xb7, 0x5d, 0x4d, 0x19, 0x61, 0x18, 0xfc, 0x27, 0xd7, 0x43, 0x0d, 0xca, 0x10, 0xc1, 0xd0, 0x60, 0x85, 0xd4, 0x48 }; static const unsigned char PRIME_P_1024[128] = { 0x50, 0x23, 0x1a, 0x89, 0xe2, 0x9c, 0x99, 0x30, 0x30, 0x48, 0x2a, 0xe7, 0x15, 0xf6, 0xee, 0x96, 0x74, 0x60, 0xd3, 0x56, 0xb7, 0x97, 0xa8, 0x57, 0x71, 0xf5, 0xdf, 0x8d, 0xb4, 0x34, 0xbd, 0xcd, 0xa3, 0xb6, 0xb2, 0xe1, 0x5d, 0xc4, 0x82, 0x7b, 0x85, 0xe7, 0x54, 0x51, 0xa1, 0x45, 0xa6, 0x22, 0x73, 0x54, 0x17, 0xc7, 0xb0, 0x82, 0xa2, 0xb7, 0x5c, 0x06, 0xdb, 0xa4, 0x96, 0x51, 0x94, 0x48, 0x55, 0x69, 0xaa, 0x36, 0xf9, 0x6f, 0xfd, 0x98, 0xc3, 0x43, 0x5b, 0x7d, 0x05, 0x41, 0xf3, 0x9c, 0x81, 0xe9, 0x3d, 0xee, 0x8d, 0x83, 0xe3, 0x75, 0x5c, 0xa7, 0x25, 0x4e, 0x4c, 0x7c, 0x1d, 0xc1, 0xc7, 0xac, 0xf5, 0x5b, 0x23, 0x6c, 0xef, 0x78, 0xb1, 0xcb, 0x9e, 0x38, 0xe5, 0x2d, 0xa0, 0x45, 0xc9, 0xd8, 0x92, 0xf6, 0x73, 0x1d, 0xce, 0xbd, 0xa0, 0x0f, 0x05, 0x42, 0x7d, 0x4f, 0x3c, 0x97 }; static const unsigned char PRIME_Q_1024[128] = { 0xe3, 0xfe, 0xf6, 0x42, 0xf7, 0x8b, 0x17, 0xf5, 0x0e, 0x36, 0x88, 0xdf, 0x6f, 0xc4, 0x19, 0xf3, 0x35, 0x5a, 0xf8, 0xa5, 0xb5, 0x00, 0x64, 0xba, 0x7b, 0x0f, 0xf5, 0xaa, 0xe0, 0x95, 0x0b, 0x87, 0x44, 0x0a, 0x40, 0x09, 0x72, 0x2f, 0xad, 0x7c, 0xae, 0x9a, 0x5a, 0xb9, 0xc2, 0x1e, 0x94, 0xf6, 0x26, 0x0f, 0x04, 0x6b, 0xcc, 0xd8, 0x8b, 0x89, 0x38, 0xe5, 0xbf, 0x7d, 0xc0, 0x5b, 0x84, 0xa0, 0x97, 0x58, 0xe7, 0x4c, 0xe3, 0xa6, 0xb5, 0x6e, 0x5d, 0x22, 0x2a, 0x22, 0x71, 0xe8, 0x4c, 0xaa, 0xf6, 0xc1, 0x71, 0x0a, 0x4f, 0x57, 0xbe, 0x71, 0x11, 0x16, 0xbb, 0x63, 0x0d, 0x35, 0x84, 0x59, 0x0a, 0xa3, 0x66, 0x5a, 0x02, 0xe7, 0x0a, 0xfa, 0x61, 0xa0, 0x1c, 0xe0, 0x10, 0xcc, 0xea, 0x87, 0xa8, 0x3e, 0x9a, 0xb6, 0xe3, 0xbf, 0x70, 0x11, 0x80, 0x0a, 0x46, 0x0b, 0x37, 0xc9, 0x8e, 0xbd }; static const unsigned char MODULUS_2048[256] = { 0x47, 0x5e, 0xf0, 0x73, 0x4a, 0xca, 0x73, 0xae, 0xf0, 0x24, 0x9c, 0x51, 0x9e, 0x1c, 0xfe, 0xb2, 0x3d, 0x07, 0x62, 0xb0, 0xf6, 0x0a, 0x46, 0x54, 0x17, 0x88, 0x6b, 0x2a, 0xf4, 0x2e, 0xdb, 0xc7, 0xaa, 0x42, 0x9a, 0xc5, 0xe9, 0x97, 0x30, 0xc6, 0xc9, 0xec, 0x4e, 0x2b, 0x92, 0x45, 0x6e, 0xf6, 0xf6, 0x45, 0x06, 0xa5, 0xc8, 0xe1, 0x62, 0x3d, 0x16, 0xa9, 0x0a, 0x17, 0x1a, 0xce, 0xb0, 0x72, 0x54, 0xb9, 0xca, 0x88, 0x1c, 0x6d, 0xda, 0xce, 0x65, 0x2e, 0x6c, 0xf3, 0x4b, 0x79, 0xd9, 0x92, 0x65, 0x17, 0x6f, 0x49, 0x10, 0x48, 0x18, 0xe9, 0x0d, 0x86, 0xb3, 0x60, 0xed, 0x22, 0x95, 0x5c, 0x95, 0x19, 0x02, 0x9b, 0xf3, 0x41, 0x2b, 0x35, 0x89, 0x7a, 0x0f, 0xc8, 0x51, 0xeb, 0xcf, 0x46, 0x13, 0xf1, 0x8f, 0x6b, 0x75, 0x81, 0x6b, 0x3d, 0x50, 0x97, 0xb9, 0xad, 0xcc, 0x8d, 0x10, 0x3b, 0xd8, 0x02, 0x8b, 0x22, 0x65, 0xcd, 0x3a, 0x67, 0x3f, 0x1f, 0xb1, 0xbe, 0x05, 0xaf, 0x9a, 0x27, 0x0b, 0x74, 0xe1, 0x6a, 0x2f, 0xa8, 0xb0, 0x0e, 0x3c, 0xc9, 0xec, 0x52, 0xe9, 0xf3, 0xa2, 0xde, 0xf6, 0xd0, 0x36, 0xd7, 0xcb, 0x12, 0x85, 0xf6, 0x58, 0x0c, 0xb4, 0x57, 0xe3, 0x62, 0xcd, 0xc3, 0xef, 0xa3, 0xed, 0x87, 0xf8, 0x56, 0xaa, 0x33, 0x70, 0x03, 0xfa, 0x41, 0x8e, 0xf6, 0x92, 0x9a, 0x69, 0x31, 0x9e, 0x4c, 0x22, 0x6b, 0x02, 0xc7, 0x2f, 0x60, 0xe5, 0x9d, 0xa8, 0x79, 0x6a, 0xa8, 0x43, 0xb1, 0x37, 0x85, 0x5e, 0x52, 0xc2, 0xe8, 0xd0, 0x0c, 0xc6, 0x0e, 0x36, 0x04, 0x40, 0x67, 0x33, 0x54, 0x5d, 0x79, 0x45, 0x69, 0x52, 0x3d, 0xa2, 0x76, 0xb7, 0xa6, 0x3c, 0xee, 0xa3, 0x6d, 0x13, 0x43, 0x97, 0x30, 0x1b, 0xb8, 0xb8, 0x3d, 0xd5, 0x01, 0x11, 0x50, 0x7a, 0xaa, 0x7d, 0x7b }; static const unsigned char PRIME_P_2048[256] = { 0xcc, 0xbf, 0x79, 0xad, 0x1f, 0x5e, 0x47, 0x08, 0x60, 0x62, 0x27, 0x4e, 0xa9, 0x81, 0x50, 0x42, 0xfd, 0x93, 0x81, 0x49, 0xa5, 0x55, 0x7c, 0x8c, 0xb3, 0xb0, 0xc3, 0x3d, 0xdc, 0xd8, 0x7c, 0x58, 0xa5, 0x37, 0x60, 0x82, 0x6a, 0x99, 0xd1, 0x96, 0x85, 0x24, 0x60, 0x76, 0x2e, 0x16, 0xa7, 0x15, 0xe4, 0x0b, 0xee, 0x58, 0x47, 0x32, 0x4a, 0xa1, 0x99, 0x11, 0xe9, 0x8b, 0xf5, 0x8e, 0x8c, 0x9a, 0xf6, 0x5e, 0x06, 0x18, 0x2b, 0xb3, 0x07, 0xc7, 0x06, 0x06, 0x9d, 0xf3, 0x94, 0xe5, 0xd0, 0x98, 0xfb, 0xe8, 0x57, 0x01, 0xeb, 0x2e, 0x88, 0x08, 0x99, 0x13, 0x83, 0x4a, 0xad, 0xba, 0x3b, 0x13, 0x4f, 0x64, 0x6f, 0x6d, 0x48, 0xf2, 0xda, 0xcb, 0xa0, 0x0a, 0x5b, 0xfd, 0x15, 0xe8, 0xb8, 0xd9, 0xc0, 0xef, 0xe1, 0xf4, 0x20, 0x95, 0x95, 0xb9, 0x20, 0x69, 0x1a, 0xee, 0xbf, 0xc4, 0xba, 0x1b, 0x28, 0x59, 0x2d, 0x88, 0xfc, 0x0f, 0x56, 0x5b, 0x0d, 0x3d, 0xbc, 0xf2, 0xe3, 0xdd, 0xa7, 0xb0, 0x2e, 0x54, 0x52, 0x66, 0x0c, 0x4b, 0xd4, 0x48, 0x5e, 0x23, 0xcb, 0x68, 0xe1, 0xfd, 0xc9, 0xf3, 0x64, 0x7f, 0x85, 0xc5, 0xee, 0x0c, 0x35, 0x55, 0xc2, 0x1c, 0xe8, 0x30, 0x73, 0x20, 0x25, 0x7f, 0xae, 0x14, 0x88, 0x87, 0xaf, 0x54, 0x12, 0xdb, 0x2c, 0xec, 0xe2, 0x40, 0x04, 0x4c, 0xd6, 0x68, 0xc7, 0x2c, 0x72, 0x19, 0xb2, 0xe6, 0xa3, 0x2f, 0x5d, 0xa0, 0xe0, 0xcd, 0x52, 0xec, 0x90, 0x78, 0xe7, 0xef, 0x52, 0x14, 0x61, 0xf2, 0xfe, 0x5d, 0x83, 0xb2, 0x40, 0xc4, 0x12, 0x50, 0x79, 0x61, 0x05, 0x12, 0x97, 0x6d, 0x1c, 0x3b, 0x65, 0xfc, 0xb0, 0xad, 0x75, 0x13, 0x30, 0x12, 0xe2, 0xc7, 0x32, 0x9c, 0xe5, 0x51, 0x77, 0x55, 0x6f, 0x07, 0xbd, 0xab, 0xb2, 0x71, 0x62, 0x24, 0x66, 0xfb }; static const unsigned char PRIME_Q_2048[256] = { 0x84, 0x2d, 0x18, 0xae, 0x53, 0xb1, 0xe4, 0x7a, 0xac, 0x1d, 0x2c, 0x7f, 0xf9, 0x1e, 0xe6, 0x56, 0xf6, 0x69, 0xce, 0x96, 0x76, 0xed, 0xc2, 0x68, 0x9f, 0x39, 0xb2, 0xcd, 0x30, 0x52, 0xc9, 0x15, 0x7e, 0x65, 0xb1, 0x62, 0x41, 0xbb, 0x9d, 0x6e, 0xb0, 0xd1, 0x5a, 0xdf, 0xb4, 0xba, 0xa9, 0x7a, 0x7f, 0x6f, 0x4b, 0x9d, 0x06, 0x21, 0xef, 0x84, 0xd1, 0xba, 0x26, 0x2f, 0x5b, 0x3b, 0x98, 0xec, 0x7b, 0x47, 0xa5, 0x49, 0x26, 0x31, 0xe2, 0x82, 0xad, 0xe5, 0x10, 0x8d, 0x02, 0xfc, 0x14, 0xc9, 0x65, 0xd9, 0xdb, 0xfd, 0x46, 0x83, 0xf7, 0x40, 0xab, 0xc8, 0xf9, 0x12, 0x0d, 0x0c, 0x7e, 0x2f, 0x79, 0xb0, 0xc9, 0x4f, 0x68, 0xf0, 0xc9, 0x1a, 0xcd, 0xbd, 0x97, 0x7a, 0x66, 0xf9, 0xa9, 0xe1, 0x59, 0xe6, 0x80, 0xec, 0x12, 0xba, 0x63, 0x2e, 0xd3, 0x6f, 0x54, 0xf4, 0x38, 0xe0, 0xea, 0xef, 0xc2, 0x4b, 0x6e, 0x25, 0xc6, 0xfd, 0x32, 0xda, 0x9a, 0x9c, 0x92, 0x71, 0x0c, 0xed, 0xe0, 0x54, 0x62, 0x33, 0x51, 0x78, 0xba, 0xa5, 0x74, 0xe2, 0x51, 0x9a, 0xa0, 0xbd, 0x55, 0xa6, 0x9e, 0x5c, 0xa1, 0x30, 0x40, 0x51, 0x74, 0x27, 0x1a, 0xfe, 0x9b, 0x92, 0xad, 0x5e, 0x82, 0xc5, 0xce, 0xae, 0x9f, 0x91, 0x24, 0xf1, 0xb3, 0x61, 0xe2, 0x25, 0x03, 0xad, 0x1c, 0xa0, 0xba, 0xd5, 0x26, 0xa2, 0xee, 0xf8, 0x33, 0xad, 0x84, 0xef, 0xc4, 0x20, 0x31, 0x37, 0xb1, 0x07, 0x04, 0xba, 0xb5, 0xce, 0x6b, 0xb2, 0xeb, 0x58, 0xa2, 0x20, 0x9e, 0xf7, 0x38, 0xc4, 0x4b, 0x71, 0x27, 0x65, 0x5e, 0xd9, 0x37, 0xc5, 0xa9, 0x37, 0xae, 0x6a, 0xc9, 0xbe, 0xaa, 0xce, 0x7e, 0xce, 0x9f, 0xb3, 0x3a, 0xe6, 0x0e, 0x98, 0x0d, 0xa7, 0x37, 0x30, 0xa6, 0x14, 0x4e, 0x38, 0xca, 0x9a, 0x53, 0x7f, 0xe0, 0x2d }; static const unsigned char MODULUS_4096[512] = { 0x69, 0xb6, 0xcc, 0x23, 0x08, 0x18, 0x6a, 0x61, 0xde, 0x0d, 0x06, 0xf0, 0x49, 0xb2, 0x4e, 0x9b, 0xaf, 0x47, 0x55, 0x32, 0x6e, 0x0d, 0xb8, 0xcb, 0x10, 0xf1, 0xe5, 0x37, 0x63, 0x7b, 0xb8, 0xd2, 0x70, 0x1c, 0xca, 0x89, 0xb9, 0x66, 0x32, 0xaf, 0x00, 0x61, 0xa0, 0x72, 0xbb, 0x99, 0x44, 0x0d, 0x56, 0x1d, 0x90, 0x0b, 0x51, 0x73, 0x1e, 0x2b, 0xae, 0x57, 0xb8, 0x73, 0x0e, 0x71, 0x40, 0x61, 0xdc, 0xc6, 0x28, 0xec, 0x74, 0x4e, 0x8b, 0xd0, 0xd4, 0xd5, 0xd6, 0xae, 0x70, 0xfa, 0x6b, 0x9c, 0x37, 0x75, 0x73, 0xd2, 0xca, 0x09, 0x91, 0x0a, 0x93, 0x00, 0x26, 0xc0, 0xa1, 0x94, 0xb4, 0xa9, 0x2b, 0x35, 0x29, 0x14, 0xfa, 0x59, 0x9c, 0xbd, 0xbc, 0x9a, 0xc5, 0xe5, 0x44, 0x62, 0x4f, 0x4d, 0x85, 0xaa, 0x75, 0x46, 0xc7, 0xf6, 0xf8, 0x97, 0xe2, 0x25, 0x27, 0x64, 0x2e, 0xb3, 0x96, 0x44, 0x70, 0x6d, 0x0f, 0xe2, 0x94, 0x9c, 0x23, 0x19, 0x00, 0xd4, 0x2a, 0x4e, 0xad, 0x1a, 0xbf, 0x10, 0x2a, 0x7b, 0x57, 0x13, 0xee, 0x2d, 0xb0, 0x6b, 0xe9, 0x90, 0x45, 0x20, 0x40, 0xef, 0xd2, 0x86, 0x64, 0xfc, 0x8f, 0x71, 0x81, 0xcc, 0xa5, 0x4e, 0x58, 0x0a, 0x6e, 0x1f, 0x90, 0x34, 0x45, 0x17, 0x98, 0x4f, 0xec, 0xfa, 0xae, 0x34, 0xae, 0x2a, 0x1b, 0xf3, 0x99, 0x14, 0x9c, 0x04, 0x48, 0xcc, 0xd9, 0x72, 0x0c, 0xfc, 0x71, 0xb0, 0xa0, 0x4a, 0x90, 0xaf, 0x84, 0xfe, 0x83, 0x74, 0x9e, 0xd6, 0x19, 0x8a, 0x31, 0x27, 0xb5, 0x8d, 0x30, 0x36, 0x0c, 0xc9, 0x92, 0x64, 0x40, 0x17, 0xd3, 0x43, 0xc9, 0x4d, 0x4c, 0x98, 0x9b, 0x38, 0xaf, 0x4a, 0xe8, 0xc4, 0x53, 0xfe, 0x18, 0xf7, 0xfd, 0x68, 0x59, 0xb4, 0xea, 0xc2, 0x93, 0x10, 0x89, 0xfe, 0x04, 0x23, 0xe8, 0x21, 0x23, 0x68, 0x50, 0xd1, 0xc1, 0x52, 0xaf, 0x9c, 0x6e, 0x00, 0xc5, 0x3f, 0xa5, 0x3d, 0x33, 0xae, 0x22, 0xd9, 0x46, 0xaa, 0x45, 0x46, 0x87, 0x27, 0x04, 0x5e, 0xe4, 0xbe, 0xe4, 0x0c, 0x32, 0x60, 0x72, 0xa7, 0x66, 0x93, 0x26, 0x61, 0xdc, 0x28, 0x3d, 0xa8, 0x6a, 0x35, 0x12, 0x65, 0xba, 0x8e, 0x55, 0x7d, 0xeb, 0xd0, 0x85, 0xb7, 0x4e, 0xc1, 0xaf, 0x1a, 0x7b, 0x1d, 0xfb, 0xb2, 0x75, 0x98, 0xf5, 0x6a, 0x56, 0x35, 0xef, 0xe7, 0x24, 0x22, 0xda, 0x2e, 0x05, 0x44, 0x9d, 0xde, 0x1a, 0xae, 0x21, 0x76, 0xf5, 0x39, 0xf3, 0x2f, 0xc6, 0xc3, 0x60, 0x33, 0x4d, 0xcb, 0x8c, 0xd1, 0x26, 0x98, 0x00, 0xed, 0xed, 0xac, 0x69, 0xb8, 0x0f, 0x71, 0xdb, 0x0e, 0xb6, 0x4e, 0x43, 0xcf, 0xbc, 0xa6, 0x76, 0xa7, 0x15, 0xf1, 0x91, 0xdc, 0xf0, 0x3f, 0xc8, 0xbf, 0x49, 0x0b, 0xfa, 0xd7, 0x95, 0x5f, 0xc7, 0x1c, 0x8e, 0x38, 0xa8, 0x58, 0x2f, 0x72, 0xe4, 0x2b, 0xda, 0x79, 0x75, 0x26, 0x75, 0xd6, 0xe4, 0x17, 0x85, 0xf3, 0xac, 0x30, 0x93, 0x35, 0xea, 0xec, 0x6f, 0xf1, 0x42, 0x58, 0x10, 0xf7, 0x94, 0xda, 0x6f, 0x1a, 0x33, 0xfb, 0xcb, 0xd3, 0xe8, 0x30, 0xc9, 0x1c, 0x2e, 0x26, 0x67, 0xb3, 0x6f, 0xe9, 0xcf, 0x72, 0xd7, 0x7e, 0xb2, 0xe5, 0x0b, 0xc0, 0xb2, 0x29, 0x90, 0xf5, 0x1b, 0xa0, 0xc8, 0xbb, 0xdb, 0xd0, 0xda, 0xac, 0x01, 0x29, 0x7b, 0x49, 0x1c, 0xdb, 0x00, 0x14, 0x34, 0x72, 0x4b, 0xe6, 0x77, 0x97, 0x86, 0xe8, 0x1a, 0x72, 0x16, 0xf8, 0x6a, 0x2c, 0x8c, 0x2a, 0xc6, 0xac, 0x91, 0xe9, 0x2d, 0xc6, 0x5e, 0x5a, 0x62, 0xf7, 0xac, 0xdc, 0xea, 0x1c, 0xea, 0x6b, 0xc3, 0xc9, 0x6b, 0xa8, 0x76, 0xff, 0xea, 0x4c, 0xce, 0x8c, 0xfc, 0xfb, 0x39, 0xf3, 0xa0, 0x73, 0x12, 0x3e, 0x92, 0x06, 0xba, 0x1f }; static const int SYMBOLS[][3] = { /* https://github.com/golang/go/blob/aadaec5/src/math/big/int_test.go#L1590 */ {0, 1, 1}, {0, -1, 1}, {1, 1, 1}, {1, -1, 1}, {0, 5, 0}, {1, 5, 1}, {2, 5, -1}, {-2, 5, -1}, {2, -5, -1}, {-2, -5, 1}, {3, 5, -1}, {5, 5, 0}, {-5, 5, 0}, {6, 5, 1}, {6, -5, 1}, {-6, 5, 1}, {-6, -5, -1}, /* https://en.wikipedia.org/wiki/Legendre_symbol#Table_of_values */ {1, 3, 1}, {1, 5, 1}, {1, 7, 1}, {1, 11, 1}, {1, 13, 1}, {1, 17, 1}, {1, 19, 1}, {1, 23, 1}, {1, 29, 1}, {1, 31, 1}, {1, 37, 1}, {1, 41, 1}, {1, 43, 1}, {1, 47, 1}, {1, 53, 1}, {1, 59, 1}, {1, 61, 1}, {1, 67, 1}, {1, 71, 1}, {1, 73, 1}, {1, 79, 1}, {1, 83, 1}, {1, 89, 1}, {1, 97, 1}, {1, 101, 1}, {1, 103, 1}, {1, 107, 1}, {1, 109, 1}, {1, 113, 1}, {1, 127, 1}, {2, 3, -1}, {2, 5, -1}, {2, 7, 1}, {2, 11, -1}, {2, 13, -1}, {2, 17, 1}, {2, 19, -1}, {2, 23, 1}, {2, 29, -1}, {2, 31, 1}, {2, 37, -1}, {2, 41, 1}, {2, 43, -1}, {2, 47, 1}, {2, 53, -1}, {2, 59, -1}, {2, 61, -1}, {2, 67, -1}, {2, 71, 1}, {2, 73, 1}, {2, 79, 1}, {2, 83, -1}, {2, 89, 1}, {2, 97, 1}, {2, 101, -1}, {2, 103, 1}, {2, 107, -1}, {2, 109, -1}, {2, 113, 1}, {2, 127, 1}, {3, 3, 0}, {3, 5, -1}, {3, 7, -1}, {3, 11, 1}, {3, 13, 1}, {3, 17, -1}, {3, 19, -1}, {3, 23, 1}, {3, 29, -1}, {3, 31, -1}, {3, 37, 1}, {3, 41, -1}, {3, 43, -1}, {3, 47, 1}, {3, 53, -1}, {3, 59, 1}, {3, 61, 1}, {3, 67, -1}, {3, 71, 1}, {3, 73, 1}, {3, 79, -1}, {3, 83, 1}, {3, 89, -1}, {3, 97, 1}, {3, 101, -1}, {3, 103, -1}, {3, 107, 1}, {3, 109, 1}, {3, 113, -1}, {3, 127, -1}, {4, 3, 1}, {4, 5, 1}, {4, 7, 1}, {4, 11, 1}, {4, 13, 1}, {4, 17, 1}, {4, 19, 1}, {4, 23, 1}, {4, 29, 1}, {4, 31, 1}, {4, 37, 1}, {4, 41, 1}, {4, 43, 1}, {4, 47, 1}, {4, 53, 1}, {4, 59, 1}, {4, 61, 1}, {4, 67, 1}, {4, 71, 1}, {4, 73, 1}, {4, 79, 1}, {4, 83, 1}, {4, 89, 1}, {4, 97, 1}, {4, 101, 1}, {4, 103, 1}, {4, 107, 1}, {4, 109, 1}, {4, 113, 1}, {4, 127, 1}, {5, 3, -1}, {5, 5, 0}, {5, 7, -1}, {5, 11, 1}, {5, 13, -1}, {5, 17, -1}, {5, 19, 1}, {5, 23, -1}, {5, 29, 1}, {5, 31, 1}, {5, 37, -1}, {5, 41, 1}, {5, 43, -1}, {5, 47, -1}, {5, 53, -1}, {5, 59, 1}, {5, 61, 1}, {5, 67, -1}, {5, 71, 1}, {5, 73, -1}, {5, 79, 1}, {5, 83, -1}, {5, 89, 1}, {5, 97, -1}, {5, 101, 1}, {5, 103, -1}, {5, 107, -1}, {5, 109, 1}, {5, 113, -1}, {5, 127, -1}, {6, 3, 0}, {6, 5, 1}, {6, 7, -1}, {6, 11, -1}, {6, 13, -1}, {6, 17, -1}, {6, 19, 1}, {6, 23, 1}, {6, 29, 1}, {6, 31, -1}, {6, 37, -1}, {6, 41, -1}, {6, 43, 1}, {6, 47, 1}, {6, 53, 1}, {6, 59, -1}, {6, 61, -1}, {6, 67, 1}, {6, 71, 1}, {6, 73, 1}, {6, 79, -1}, {6, 83, -1}, {6, 89, -1}, {6, 97, 1}, {6, 101, 1}, {6, 103, -1}, {6, 107, -1}, {6, 109, -1}, {6, 113, -1}, {6, 127, -1}, {7, 3, 1}, {7, 5, -1}, {7, 7, 0}, {7, 11, -1}, {7, 13, -1}, {7, 17, -1}, {7, 19, 1}, {7, 23, -1}, {7, 29, 1}, {7, 31, 1}, {7, 37, 1}, {7, 41, -1}, {7, 43, -1}, {7, 47, 1}, {7, 53, 1}, {7, 59, 1}, {7, 61, -1}, {7, 67, -1}, {7, 71, -1}, {7, 73, -1}, {7, 79, -1}, {7, 83, 1}, {7, 89, -1}, {7, 97, -1}, {7, 101, -1}, {7, 103, 1}, {7, 107, -1}, {7, 109, 1}, {7, 113, 1}, {7, 127, -1}, {8, 3, -1}, {8, 5, -1}, {8, 7, 1}, {8, 11, -1}, {8, 13, -1}, {8, 17, 1}, {8, 19, -1}, {8, 23, 1}, {8, 29, -1}, {8, 31, 1}, {8, 37, -1}, {8, 41, 1}, {8, 43, -1}, {8, 47, 1}, {8, 53, -1}, {8, 59, -1}, {8, 61, -1}, {8, 67, -1}, {8, 71, 1}, {8, 73, 1}, {8, 79, 1}, {8, 83, -1}, {8, 89, 1}, {8, 97, 1}, {8, 101, -1}, {8, 103, 1}, {8, 107, -1}, {8, 109, -1}, {8, 113, 1}, {8, 127, 1}, {9, 3, 0}, {9, 5, 1}, {9, 7, 1}, {9, 11, 1}, {9, 13, 1}, {9, 17, 1}, {9, 19, 1}, {9, 23, 1}, {9, 29, 1}, {9, 31, 1}, {9, 37, 1}, {9, 41, 1}, {9, 43, 1}, {9, 47, 1}, {9, 53, 1}, {9, 59, 1}, {9, 61, 1}, {9, 67, 1}, {9, 71, 1}, {9, 73, 1}, {9, 79, 1}, {9, 83, 1}, {9, 89, 1}, {9, 97, 1}, {9, 101, 1}, {9, 103, 1}, {9, 107, 1}, {9, 109, 1}, {9, 113, 1}, {9, 127, 1}, {10, 3, 1}, {10, 5, 0}, {10, 7, -1}, {10, 11, -1}, {10, 13, 1}, {10, 17, -1}, {10, 19, -1}, {10, 23, -1}, {10, 29, -1}, {10, 31, 1}, {10, 37, 1}, {10, 41, 1}, {10, 43, 1}, {10, 47, -1}, {10, 53, 1}, {10, 59, -1}, {10, 61, -1}, {10, 67, 1}, {10, 71, 1}, {10, 73, -1}, {10, 79, 1}, {10, 83, 1}, {10, 89, 1}, {10, 97, -1}, {10, 101, -1}, {10, 103, -1}, {10, 107, 1}, {10, 109, -1}, {10, 113, -1}, {10, 127, -1}, {11, 3, -1}, {11, 5, 1}, {11, 7, 1}, {11, 11, 0}, {11, 13, -1}, {11, 17, -1}, {11, 19, 1}, {11, 23, -1}, {11, 29, -1}, {11, 31, -1}, {11, 37, 1}, {11, 41, -1}, {11, 43, 1}, {11, 47, -1}, {11, 53, 1}, {11, 59, -1}, {11, 61, -1}, {11, 67, -1}, {11, 71, -1}, {11, 73, -1}, {11, 79, 1}, {11, 83, 1}, {11, 89, 1}, {11, 97, 1}, {11, 101, -1}, {11, 103, -1}, {11, 107, 1}, {11, 109, -1}, {11, 113, 1}, {11, 127, 1}, {12, 3, 0}, {12, 5, -1}, {12, 7, -1}, {12, 11, 1}, {12, 13, 1}, {12, 17, -1}, {12, 19, -1}, {12, 23, 1}, {12, 29, -1}, {12, 31, -1}, {12, 37, 1}, {12, 41, -1}, {12, 43, -1}, {12, 47, 1}, {12, 53, -1}, {12, 59, 1}, {12, 61, 1}, {12, 67, -1}, {12, 71, 1}, {12, 73, 1}, {12, 79, -1}, {12, 83, 1}, {12, 89, -1}, {12, 97, 1}, {12, 101, -1}, {12, 103, -1}, {12, 107, 1}, {12, 109, 1}, {12, 113, -1}, {12, 127, -1}, {13, 3, 1}, {13, 5, -1}, {13, 7, -1}, {13, 11, -1}, {13, 13, 0}, {13, 17, 1}, {13, 19, -1}, {13, 23, 1}, {13, 29, 1}, {13, 31, -1}, {13, 37, -1}, {13, 41, -1}, {13, 43, 1}, {13, 47, -1}, {13, 53, 1}, {13, 59, -1}, {13, 61, 1}, {13, 67, -1}, {13, 71, -1}, {13, 73, -1}, {13, 79, 1}, {13, 83, -1}, {13, 89, -1}, {13, 97, -1}, {13, 101, 1}, {13, 103, 1}, {13, 107, 1}, {13, 109, -1}, {13, 113, 1}, {13, 127, 1}, {14, 3, -1}, {14, 5, 1}, {14, 7, 0}, {14, 11, 1}, {14, 13, 1}, {14, 17, -1}, {14, 19, -1}, {14, 23, -1}, {14, 29, -1}, {14, 31, 1}, {14, 37, -1}, {14, 41, -1}, {14, 43, 1}, {14, 47, 1}, {14, 53, -1}, {14, 59, -1}, {14, 61, 1}, {14, 67, 1}, {14, 71, -1}, {14, 73, -1}, {14, 79, -1}, {14, 83, -1}, {14, 89, -1}, {14, 97, -1}, {14, 101, 1}, {14, 103, 1}, {14, 107, 1}, {14, 109, -1}, {14, 113, 1}, {14, 127, -1}, {15, 3, 0}, {15, 5, 0}, {15, 7, 1}, {15, 11, 1}, {15, 13, -1}, {15, 17, 1}, {15, 19, -1}, {15, 23, -1}, {15, 29, -1}, {15, 31, -1}, {15, 37, -1}, {15, 41, -1}, {15, 43, 1}, {15, 47, -1}, {15, 53, 1}, {15, 59, 1}, {15, 61, 1}, {15, 67, 1}, {15, 71, 1}, {15, 73, -1}, {15, 79, -1}, {15, 83, -1}, {15, 89, -1}, {15, 97, -1}, {15, 101, -1}, {15, 103, 1}, {15, 107, -1}, {15, 109, 1}, {15, 113, 1}, {15, 127, 1}, {16, 3, 1}, {16, 5, 1}, {16, 7, 1}, {16, 11, 1}, {16, 13, 1}, {16, 17, 1}, {16, 19, 1}, {16, 23, 1}, {16, 29, 1}, {16, 31, 1}, {16, 37, 1}, {16, 41, 1}, {16, 43, 1}, {16, 47, 1}, {16, 53, 1}, {16, 59, 1}, {16, 61, 1}, {16, 67, 1}, {16, 71, 1}, {16, 73, 1}, {16, 79, 1}, {16, 83, 1}, {16, 89, 1}, {16, 97, 1}, {16, 101, 1}, {16, 103, 1}, {16, 107, 1}, {16, 109, 1}, {16, 113, 1}, {16, 127, 1}, {17, 3, -1}, {17, 5, -1}, {17, 7, -1}, {17, 11, -1}, {17, 13, 1}, {17, 17, 0}, {17, 19, 1}, {17, 23, -1}, {17, 29, -1}, {17, 31, -1}, {17, 37, -1}, {17, 41, -1}, {17, 43, 1}, {17, 47, 1}, {17, 53, 1}, {17, 59, 1}, {17, 61, -1}, {17, 67, 1}, {17, 71, -1}, {17, 73, -1}, {17, 79, -1}, {17, 83, 1}, {17, 89, 1}, {17, 97, -1}, {17, 101, 1}, {17, 103, 1}, {17, 107, -1}, {17, 109, -1}, {17, 113, -1}, {17, 127, 1}, {18, 3, 0}, {18, 5, -1}, {18, 7, 1}, {18, 11, -1}, {18, 13, -1}, {18, 17, 1}, {18, 19, -1}, {18, 23, 1}, {18, 29, -1}, {18, 31, 1}, {18, 37, -1}, {18, 41, 1}, {18, 43, -1}, {18, 47, 1}, {18, 53, -1}, {18, 59, -1}, {18, 61, -1}, {18, 67, -1}, {18, 71, 1}, {18, 73, 1}, {18, 79, 1}, {18, 83, -1}, {18, 89, 1}, {18, 97, 1}, {18, 101, -1}, {18, 103, 1}, {18, 107, -1}, {18, 109, -1}, {18, 113, 1}, {18, 127, 1}, {19, 3, 1}, {19, 5, 1}, {19, 7, -1}, {19, 11, -1}, {19, 13, -1}, {19, 17, 1}, {19, 19, 0}, {19, 23, -1}, {19, 29, -1}, {19, 31, 1}, {19, 37, -1}, {19, 41, -1}, {19, 43, -1}, {19, 47, -1}, {19, 53, -1}, {19, 59, 1}, {19, 61, 1}, {19, 67, 1}, {19, 71, 1}, {19, 73, 1}, {19, 79, 1}, {19, 83, -1}, {19, 89, -1}, {19, 97, -1}, {19, 101, 1}, {19, 103, 1}, {19, 107, 1}, {19, 109, -1}, {19, 113, -1}, {19, 127, 1}, {20, 3, -1}, {20, 5, 0}, {20, 7, -1}, {20, 11, 1}, {20, 13, -1}, {20, 17, -1}, {20, 19, 1}, {20, 23, -1}, {20, 29, 1}, {20, 31, 1}, {20, 37, -1}, {20, 41, 1}, {20, 43, -1}, {20, 47, -1}, {20, 53, -1}, {20, 59, 1}, {20, 61, 1}, {20, 67, -1}, {20, 71, 1}, {20, 73, -1}, {20, 79, 1}, {20, 83, -1}, {20, 89, 1}, {20, 97, -1}, {20, 101, 1}, {20, 103, -1}, {20, 107, -1}, {20, 109, 1}, {20, 113, -1}, {20, 127, -1}, {21, 3, 0}, {21, 5, 1}, {21, 7, 0}, {21, 11, -1}, {21, 13, -1}, {21, 17, 1}, {21, 19, -1}, {21, 23, -1}, {21, 29, -1}, {21, 31, -1}, {21, 37, 1}, {21, 41, 1}, {21, 43, 1}, {21, 47, 1}, {21, 53, -1}, {21, 59, 1}, {21, 61, -1}, {21, 67, 1}, {21, 71, -1}, {21, 73, -1}, {21, 79, 1}, {21, 83, 1}, {21, 89, 1}, {21, 97, -1}, {21, 101, 1}, {21, 103, -1}, {21, 107, -1}, {21, 109, 1}, {21, 113, -1}, {21, 127, 1}, {22, 3, 1}, {22, 5, -1}, {22, 7, 1}, {22, 11, 0}, {22, 13, 1}, {22, 17, -1}, {22, 19, -1}, {22, 23, -1}, {22, 29, 1}, {22, 31, -1}, {22, 37, -1}, {22, 41, -1}, {22, 43, -1}, {22, 47, -1}, {22, 53, -1}, {22, 59, 1}, {22, 61, 1}, {22, 67, 1}, {22, 71, -1}, {22, 73, -1}, {22, 79, 1}, {22, 83, -1}, {22, 89, 1}, {22, 97, 1}, {22, 101, 1}, {22, 103, -1}, {22, 107, -1}, {22, 109, 1}, {22, 113, 1}, {22, 127, 1}, {23, 3, -1}, {23, 5, -1}, {23, 7, 1}, {23, 11, 1}, {23, 13, 1}, {23, 17, -1}, {23, 19, 1}, {23, 23, 0}, {23, 29, 1}, {23, 31, -1}, {23, 37, -1}, {23, 41, 1}, {23, 43, 1}, {23, 47, -1}, {23, 53, -1}, {23, 59, -1}, {23, 61, -1}, {23, 67, 1}, {23, 71, -1}, {23, 73, 1}, {23, 79, 1}, {23, 83, 1}, {23, 89, -1}, {23, 97, -1}, {23, 101, 1}, {23, 103, 1}, {23, 107, 1}, {23, 109, -1}, {23, 113, -1}, {23, 127, -1}, {24, 3, 0}, {24, 5, 1}, {24, 7, -1}, {24, 11, -1}, {24, 13, -1}, {24, 17, -1}, {24, 19, 1}, {24, 23, 1}, {24, 29, 1}, {24, 31, -1}, {24, 37, -1}, {24, 41, -1}, {24, 43, 1}, {24, 47, 1}, {24, 53, 1}, {24, 59, -1}, {24, 61, -1}, {24, 67, 1}, {24, 71, 1}, {24, 73, 1}, {24, 79, -1}, {24, 83, -1}, {24, 89, -1}, {24, 97, 1}, {24, 101, 1}, {24, 103, -1}, {24, 107, -1}, {24, 109, -1}, {24, 113, -1}, {24, 127, -1}, {25, 3, 1}, {25, 5, 0}, {25, 7, 1}, {25, 11, 1}, {25, 13, 1}, {25, 17, 1}, {25, 19, 1}, {25, 23, 1}, {25, 29, 1}, {25, 31, 1}, {25, 37, 1}, {25, 41, 1}, {25, 43, 1}, {25, 47, 1}, {25, 53, 1}, {25, 59, 1}, {25, 61, 1}, {25, 67, 1}, {25, 71, 1}, {25, 73, 1}, {25, 79, 1}, {25, 83, 1}, {25, 89, 1}, {25, 97, 1}, {25, 101, 1}, {25, 103, 1}, {25, 107, 1}, {25, 109, 1}, {25, 113, 1}, {25, 127, 1}, {26, 3, -1}, {26, 5, 1}, {26, 7, -1}, {26, 11, 1}, {26, 13, 0}, {26, 17, 1}, {26, 19, 1}, {26, 23, 1}, {26, 29, -1}, {26, 31, -1}, {26, 37, 1}, {26, 41, -1}, {26, 43, -1}, {26, 47, -1}, {26, 53, -1}, {26, 59, 1}, {26, 61, -1}, {26, 67, 1}, {26, 71, -1}, {26, 73, -1}, {26, 79, 1}, {26, 83, 1}, {26, 89, -1}, {26, 97, -1}, {26, 101, -1}, {26, 103, 1}, {26, 107, -1}, {26, 109, 1}, {26, 113, 1}, {26, 127, 1}, {27, 3, 0}, {27, 5, -1}, {27, 7, -1}, {27, 11, 1}, {27, 13, 1}, {27, 17, -1}, {27, 19, -1}, {27, 23, 1}, {27, 29, -1}, {27, 31, -1}, {27, 37, 1}, {27, 41, -1}, {27, 43, -1}, {27, 47, 1}, {27, 53, -1}, {27, 59, 1}, {27, 61, 1}, {27, 67, -1}, {27, 71, 1}, {27, 73, 1}, {27, 79, -1}, {27, 83, 1}, {27, 89, -1}, {27, 97, 1}, {27, 101, -1}, {27, 103, -1}, {27, 107, 1}, {27, 109, 1}, {27, 113, -1}, {27, 127, -1}, {28, 3, 1}, {28, 5, -1}, {28, 7, 0}, {28, 11, -1}, {28, 13, -1}, {28, 17, -1}, {28, 19, 1}, {28, 23, -1}, {28, 29, 1}, {28, 31, 1}, {28, 37, 1}, {28, 41, -1}, {28, 43, -1}, {28, 47, 1}, {28, 53, 1}, {28, 59, 1}, {28, 61, -1}, {28, 67, -1}, {28, 71, -1}, {28, 73, -1}, {28, 79, -1}, {28, 83, 1}, {28, 89, -1}, {28, 97, -1}, {28, 101, -1}, {28, 103, 1}, {28, 107, -1}, {28, 109, 1}, {28, 113, 1}, {28, 127, -1}, {29, 3, -1}, {29, 5, 1}, {29, 7, 1}, {29, 11, -1}, {29, 13, 1}, {29, 17, -1}, {29, 19, -1}, {29, 23, 1}, {29, 29, 0}, {29, 31, -1}, {29, 37, -1}, {29, 41, -1}, {29, 43, -1}, {29, 47, -1}, {29, 53, 1}, {29, 59, 1}, {29, 61, -1}, {29, 67, 1}, {29, 71, 1}, {29, 73, -1}, {29, 79, -1}, {29, 83, 1}, {29, 89, -1}, {29, 97, -1}, {29, 101, -1}, {29, 103, 1}, {29, 107, 1}, {29, 109, 1}, {29, 113, -1}, {29, 127, -1}, {30, 3, 0}, {30, 5, 0}, {30, 7, 1}, {30, 11, -1}, {30, 13, 1}, {30, 17, 1}, {30, 19, 1}, {30, 23, -1}, {30, 29, 1}, {30, 31, -1}, {30, 37, 1}, {30, 41, -1}, {30, 43, -1}, {30, 47, -1}, {30, 53, -1}, {30, 59, -1}, {30, 61, -1}, {30, 67, -1}, {30, 71, 1}, {30, 73, -1}, {30, 79, -1}, {30, 83, 1}, {30, 89, -1}, {30, 97, -1}, {30, 101, 1}, {30, 103, 1}, {30, 107, 1}, {30, 109, -1}, {30, 113, 1}, {30, 127, 1}, {12345, 331, -1}, /* https://en.wikipedia.org/wiki/Jacobi_symbol#Table_of_values */ {1, 1, 1}, {1, 3, 1}, {1, 5, 1}, {1, 7, 1}, {1, 9, 1}, {1, 11, 1}, {1, 13, 1}, {1, 15, 1}, {1, 17, 1}, {1, 19, 1}, {1, 21, 1}, {1, 23, 1}, {1, 25, 1}, {1, 27, 1}, {1, 29, 1}, {1, 31, 1}, {1, 33, 1}, {1, 35, 1}, {1, 37, 1}, {1, 39, 1}, {1, 41, 1}, {1, 43, 1}, {1, 45, 1}, {1, 47, 1}, {1, 49, 1}, {1, 51, 1}, {1, 53, 1}, {1, 55, 1}, {1, 57, 1}, {1, 59, 1}, {2, 1, 1}, {2, 3, -1}, {2, 5, -1}, {2, 7, 1}, {2, 9, 1}, {2, 11, -1}, {2, 13, -1}, {2, 15, 1}, {2, 17, 1}, {2, 19, -1}, {2, 21, -1}, {2, 23, 1}, {2, 25, 1}, {2, 27, -1}, {2, 29, -1}, {2, 31, 1}, {2, 33, 1}, {2, 35, -1}, {2, 37, -1}, {2, 39, 1}, {2, 41, 1}, {2, 43, -1}, {2, 45, -1}, {2, 47, 1}, {2, 49, 1}, {2, 51, -1}, {2, 53, -1}, {2, 55, 1}, {2, 57, 1}, {2, 59, -1}, {3, 1, 1}, {3, 3, 0}, {3, 5, -1}, {3, 7, -1}, {3, 9, 0}, {3, 11, 1}, {3, 13, 1}, {3, 15, 0}, {3, 17, -1}, {3, 19, -1}, {3, 21, 0}, {3, 23, 1}, {3, 25, 1}, {3, 27, 0}, {3, 29, -1}, {3, 31, -1}, {3, 33, 0}, {3, 35, 1}, {3, 37, 1}, {3, 39, 0}, {3, 41, -1}, {3, 43, -1}, {3, 45, 0}, {3, 47, 1}, {3, 49, 1}, {3, 51, 0}, {3, 53, -1}, {3, 55, -1}, {3, 57, 0}, {3, 59, 1}, {4, 1, 1}, {4, 3, 1}, {4, 5, 1}, {4, 7, 1}, {4, 9, 1}, {4, 11, 1}, {4, 13, 1}, {4, 15, 1}, {4, 17, 1}, {4, 19, 1}, {4, 21, 1}, {4, 23, 1}, {4, 25, 1}, {4, 27, 1}, {4, 29, 1}, {4, 31, 1}, {4, 33, 1}, {4, 35, 1}, {4, 37, 1}, {4, 39, 1}, {4, 41, 1}, {4, 43, 1}, {4, 45, 1}, {4, 47, 1}, {4, 49, 1}, {4, 51, 1}, {4, 53, 1}, {4, 55, 1}, {4, 57, 1}, {4, 59, 1}, {5, 1, 1}, {5, 3, -1}, {5, 5, 0}, {5, 7, -1}, {5, 9, 1}, {5, 11, 1}, {5, 13, -1}, {5, 15, 0}, {5, 17, -1}, {5, 19, 1}, {5, 21, 1}, {5, 23, -1}, {5, 25, 0}, {5, 27, -1}, {5, 29, 1}, {5, 31, 1}, {5, 33, -1}, {5, 35, 0}, {5, 37, -1}, {5, 39, 1}, {5, 41, 1}, {5, 43, -1}, {5, 45, 0}, {5, 47, -1}, {5, 49, 1}, {5, 51, 1}, {5, 53, -1}, {5, 55, 0}, {5, 57, -1}, {5, 59, 1}, {6, 1, 1}, {6, 3, 0}, {6, 5, 1}, {6, 7, -1}, {6, 9, 0}, {6, 11, -1}, {6, 13, -1}, {6, 15, 0}, {6, 17, -1}, {6, 19, 1}, {6, 21, 0}, {6, 23, 1}, {6, 25, 1}, {6, 27, 0}, {6, 29, 1}, {6, 31, -1}, {6, 33, 0}, {6, 35, -1}, {6, 37, -1}, {6, 39, 0}, {6, 41, -1}, {6, 43, 1}, {6, 45, 0}, {6, 47, 1}, {6, 49, 1}, {6, 51, 0}, {6, 53, 1}, {6, 55, -1}, {6, 57, 0}, {6, 59, -1}, {7, 1, 1}, {7, 3, 1}, {7, 5, -1}, {7, 7, 0}, {7, 9, 1}, {7, 11, -1}, {7, 13, -1}, {7, 15, -1}, {7, 17, -1}, {7, 19, 1}, {7, 21, 0}, {7, 23, -1}, {7, 25, 1}, {7, 27, 1}, {7, 29, 1}, {7, 31, 1}, {7, 33, -1}, {7, 35, 0}, {7, 37, 1}, {7, 39, -1}, {7, 41, -1}, {7, 43, -1}, {7, 45, -1}, {7, 47, 1}, {7, 49, 0}, {7, 51, -1}, {7, 53, 1}, {7, 55, 1}, {7, 57, 1}, {7, 59, 1}, {8, 1, 1}, {8, 3, -1}, {8, 5, -1}, {8, 7, 1}, {8, 9, 1}, {8, 11, -1}, {8, 13, -1}, {8, 15, 1}, {8, 17, 1}, {8, 19, -1}, {8, 21, -1}, {8, 23, 1}, {8, 25, 1}, {8, 27, -1}, {8, 29, -1}, {8, 31, 1}, {8, 33, 1}, {8, 35, -1}, {8, 37, -1}, {8, 39, 1}, {8, 41, 1}, {8, 43, -1}, {8, 45, -1}, {8, 47, 1}, {8, 49, 1}, {8, 51, -1}, {8, 53, -1}, {8, 55, 1}, {8, 57, 1}, {8, 59, -1}, {9, 1, 1}, {9, 3, 0}, {9, 5, 1}, {9, 7, 1}, {9, 9, 0}, {9, 11, 1}, {9, 13, 1}, {9, 15, 0}, {9, 17, 1}, {9, 19, 1}, {9, 21, 0}, {9, 23, 1}, {9, 25, 1}, {9, 27, 0}, {9, 29, 1}, {9, 31, 1}, {9, 33, 0}, {9, 35, 1}, {9, 37, 1}, {9, 39, 0}, {9, 41, 1}, {9, 43, 1}, {9, 45, 0}, {9, 47, 1}, {9, 49, 1}, {9, 51, 0}, {9, 53, 1}, {9, 55, 1}, {9, 57, 0}, {9, 59, 1}, {10, 1, 1}, {10, 3, 1}, {10, 5, 0}, {10, 7, -1}, {10, 9, 1}, {10, 11, -1}, {10, 13, 1}, {10, 15, 0}, {10, 17, -1}, {10, 19, -1}, {10, 21, -1}, {10, 23, -1}, {10, 25, 0}, {10, 27, 1}, {10, 29, -1}, {10, 31, 1}, {10, 33, -1}, {10, 35, 0}, {10, 37, 1}, {10, 39, 1}, {10, 41, 1}, {10, 43, 1}, {10, 45, 0}, {10, 47, -1}, {10, 49, 1}, {10, 51, -1}, {10, 53, 1}, {10, 55, 0}, {10, 57, -1}, {10, 59, -1}, {11, 1, 1}, {11, 3, -1}, {11, 5, 1}, {11, 7, 1}, {11, 9, 1}, {11, 11, 0}, {11, 13, -1}, {11, 15, -1}, {11, 17, -1}, {11, 19, 1}, {11, 21, -1}, {11, 23, -1}, {11, 25, 1}, {11, 27, -1}, {11, 29, -1}, {11, 31, -1}, {11, 33, 0}, {11, 35, 1}, {11, 37, 1}, {11, 39, 1}, {11, 41, -1}, {11, 43, 1}, {11, 45, 1}, {11, 47, -1}, {11, 49, 1}, {11, 51, 1}, {11, 53, 1}, {11, 55, 0}, {11, 57, -1}, {11, 59, -1}, {12, 1, 1}, {12, 3, 0}, {12, 5, -1}, {12, 7, -1}, {12, 9, 0}, {12, 11, 1}, {12, 13, 1}, {12, 15, 0}, {12, 17, -1}, {12, 19, -1}, {12, 21, 0}, {12, 23, 1}, {12, 25, 1}, {12, 27, 0}, {12, 29, -1}, {12, 31, -1}, {12, 33, 0}, {12, 35, 1}, {12, 37, 1}, {12, 39, 0}, {12, 41, -1}, {12, 43, -1}, {12, 45, 0}, {12, 47, 1}, {12, 49, 1}, {12, 51, 0}, {12, 53, -1}, {12, 55, -1}, {12, 57, 0}, {12, 59, 1}, {13, 1, 1}, {13, 3, 1}, {13, 5, -1}, {13, 7, -1}, {13, 9, 1}, {13, 11, -1}, {13, 13, 0}, {13, 15, -1}, {13, 17, 1}, {13, 19, -1}, {13, 21, -1}, {13, 23, 1}, {13, 25, 1}, {13, 27, 1}, {13, 29, 1}, {13, 31, -1}, {13, 33, -1}, {13, 35, 1}, {13, 37, -1}, {13, 39, 0}, {13, 41, -1}, {13, 43, 1}, {13, 45, -1}, {13, 47, -1}, {13, 49, 1}, {13, 51, 1}, {13, 53, 1}, {13, 55, 1}, {13, 57, -1}, {13, 59, -1}, {14, 1, 1}, {14, 3, -1}, {14, 5, 1}, {14, 7, 0}, {14, 9, 1}, {14, 11, 1}, {14, 13, 1}, {14, 15, -1}, {14, 17, -1}, {14, 19, -1}, {14, 21, 0}, {14, 23, -1}, {14, 25, 1}, {14, 27, -1}, {14, 29, -1}, {14, 31, 1}, {14, 33, -1}, {14, 35, 0}, {14, 37, -1}, {14, 39, -1}, {14, 41, -1}, {14, 43, 1}, {14, 45, 1}, {14, 47, 1}, {14, 49, 0}, {14, 51, 1}, {14, 53, -1}, {14, 55, 1}, {14, 57, 1}, {14, 59, -1}, {15, 1, 1}, {15, 3, 0}, {15, 5, 0}, {15, 7, 1}, {15, 9, 0}, {15, 11, 1}, {15, 13, -1}, {15, 15, 0}, {15, 17, 1}, {15, 19, -1}, {15, 21, 0}, {15, 23, -1}, {15, 25, 0}, {15, 27, 0}, {15, 29, -1}, {15, 31, -1}, {15, 33, 0}, {15, 35, 0}, {15, 37, -1}, {15, 39, 0}, {15, 41, -1}, {15, 43, 1}, {15, 45, 0}, {15, 47, -1}, {15, 49, 1}, {15, 51, 0}, {15, 53, 1}, {15, 55, 0}, {15, 57, 0}, {15, 59, 1}, {16, 1, 1}, {16, 3, 1}, {16, 5, 1}, {16, 7, 1}, {16, 9, 1}, {16, 11, 1}, {16, 13, 1}, {16, 15, 1}, {16, 17, 1}, {16, 19, 1}, {16, 21, 1}, {16, 23, 1}, {16, 25, 1}, {16, 27, 1}, {16, 29, 1}, {16, 31, 1}, {16, 33, 1}, {16, 35, 1}, {16, 37, 1}, {16, 39, 1}, {16, 41, 1}, {16, 43, 1}, {16, 45, 1}, {16, 47, 1}, {16, 49, 1}, {16, 51, 1}, {16, 53, 1}, {16, 55, 1}, {16, 57, 1}, {16, 59, 1}, {17, 1, 1}, {17, 3, -1}, {17, 5, -1}, {17, 7, -1}, {17, 9, 1}, {17, 11, -1}, {17, 13, 1}, {17, 15, 1}, {17, 17, 0}, {17, 19, 1}, {17, 21, 1}, {17, 23, -1}, {17, 25, 1}, {17, 27, -1}, {17, 29, -1}, {17, 31, -1}, {17, 33, 1}, {17, 35, 1}, {17, 37, -1}, {17, 39, -1}, {17, 41, -1}, {17, 43, 1}, {17, 45, -1}, {17, 47, 1}, {17, 49, 1}, {17, 51, 0}, {17, 53, 1}, {17, 55, 1}, {17, 57, -1}, {17, 59, 1}, {18, 1, 1}, {18, 3, 0}, {18, 5, -1}, {18, 7, 1}, {18, 9, 0}, {18, 11, -1}, {18, 13, -1}, {18, 15, 0}, {18, 17, 1}, {18, 19, -1}, {18, 21, 0}, {18, 23, 1}, {18, 25, 1}, {18, 27, 0}, {18, 29, -1}, {18, 31, 1}, {18, 33, 0}, {18, 35, -1}, {18, 37, -1}, {18, 39, 0}, {18, 41, 1}, {18, 43, -1}, {18, 45, 0}, {18, 47, 1}, {18, 49, 1}, {18, 51, 0}, {18, 53, -1}, {18, 55, 1}, {18, 57, 0}, {18, 59, -1}, {19, 1, 1}, {19, 3, 1}, {19, 5, 1}, {19, 7, -1}, {19, 9, 1}, {19, 11, -1}, {19, 13, -1}, {19, 15, 1}, {19, 17, 1}, {19, 19, 0}, {19, 21, -1}, {19, 23, -1}, {19, 25, 1}, {19, 27, 1}, {19, 29, -1}, {19, 31, 1}, {19, 33, -1}, {19, 35, -1}, {19, 37, -1}, {19, 39, -1}, {19, 41, -1}, {19, 43, -1}, {19, 45, 1}, {19, 47, -1}, {19, 49, 1}, {19, 51, 1}, {19, 53, -1}, {19, 55, -1}, {19, 57, 0}, {19, 59, 1}, {20, 1, 1}, {20, 3, -1}, {20, 5, 0}, {20, 7, -1}, {20, 9, 1}, {20, 11, 1}, {20, 13, -1}, {20, 15, 0}, {20, 17, -1}, {20, 19, 1}, {20, 21, 1}, {20, 23, -1}, {20, 25, 0}, {20, 27, -1}, {20, 29, 1}, {20, 31, 1}, {20, 33, -1}, {20, 35, 0}, {20, 37, -1}, {20, 39, 1}, {20, 41, 1}, {20, 43, -1}, {20, 45, 0}, {20, 47, -1}, {20, 49, 1}, {20, 51, 1}, {20, 53, -1}, {20, 55, 0}, {20, 57, -1}, {20, 59, 1}, {21, 1, 1}, {21, 3, 0}, {21, 5, 1}, {21, 7, 0}, {21, 9, 0}, {21, 11, -1}, {21, 13, -1}, {21, 15, 0}, {21, 17, 1}, {21, 19, -1}, {21, 21, 0}, {21, 23, -1}, {21, 25, 1}, {21, 27, 0}, {21, 29, -1}, {21, 31, -1}, {21, 33, 0}, {21, 35, 0}, {21, 37, 1}, {21, 39, 0}, {21, 41, 1}, {21, 43, 1}, {21, 45, 0}, {21, 47, 1}, {21, 49, 0}, {21, 51, 0}, {21, 53, -1}, {21, 55, -1}, {21, 57, 0}, {21, 59, 1}, {22, 1, 1}, {22, 3, 1}, {22, 5, -1}, {22, 7, 1}, {22, 9, 1}, {22, 11, 0}, {22, 13, 1}, {22, 15, -1}, {22, 17, -1}, {22, 19, -1}, {22, 21, 1}, {22, 23, -1}, {22, 25, 1}, {22, 27, 1}, {22, 29, 1}, {22, 31, -1}, {22, 33, 0}, {22, 35, -1}, {22, 37, -1}, {22, 39, 1}, {22, 41, -1}, {22, 43, -1}, {22, 45, -1}, {22, 47, -1}, {22, 49, 1}, {22, 51, -1}, {22, 53, -1}, {22, 55, 0}, {22, 57, -1}, {22, 59, 1}, {23, 1, 1}, {23, 3, -1}, {23, 5, -1}, {23, 7, 1}, {23, 9, 1}, {23, 11, 1}, {23, 13, 1}, {23, 15, 1}, {23, 17, -1}, {23, 19, 1}, {23, 21, -1}, {23, 23, 0}, {23, 25, 1}, {23, 27, -1}, {23, 29, 1}, {23, 31, -1}, {23, 33, -1}, {23, 35, -1}, {23, 37, -1}, {23, 39, -1}, {23, 41, 1}, {23, 43, 1}, {23, 45, -1}, {23, 47, -1}, {23, 49, 1}, {23, 51, 1}, {23, 53, -1}, {23, 55, -1}, {23, 57, -1}, {23, 59, -1}, {24, 1, 1}, {24, 3, 0}, {24, 5, 1}, {24, 7, -1}, {24, 9, 0}, {24, 11, -1}, {24, 13, -1}, {24, 15, 0}, {24, 17, -1}, {24, 19, 1}, {24, 21, 0}, {24, 23, 1}, {24, 25, 1}, {24, 27, 0}, {24, 29, 1}, {24, 31, -1}, {24, 33, 0}, {24, 35, -1}, {24, 37, -1}, {24, 39, 0}, {24, 41, -1}, {24, 43, 1}, {24, 45, 0}, {24, 47, 1}, {24, 49, 1}, {24, 51, 0}, {24, 53, 1}, {24, 55, -1}, {24, 57, 0}, {24, 59, -1}, {25, 1, 1}, {25, 3, 1}, {25, 5, 0}, {25, 7, 1}, {25, 9, 1}, {25, 11, 1}, {25, 13, 1}, {25, 15, 0}, {25, 17, 1}, {25, 19, 1}, {25, 21, 1}, {25, 23, 1}, {25, 25, 0}, {25, 27, 1}, {25, 29, 1}, {25, 31, 1}, {25, 33, 1}, {25, 35, 0}, {25, 37, 1}, {25, 39, 1}, {25, 41, 1}, {25, 43, 1}, {25, 45, 0}, {25, 47, 1}, {25, 49, 1}, {25, 51, 1}, {25, 53, 1}, {25, 55, 0}, {25, 57, 1}, {25, 59, 1}, {26, 1, 1}, {26, 3, -1}, {26, 5, 1}, {26, 7, -1}, {26, 9, 1}, {26, 11, 1}, {26, 13, 0}, {26, 15, -1}, {26, 17, 1}, {26, 19, 1}, {26, 21, 1}, {26, 23, 1}, {26, 25, 1}, {26, 27, -1}, {26, 29, -1}, {26, 31, -1}, {26, 33, -1}, {26, 35, -1}, {26, 37, 1}, {26, 39, 0}, {26, 41, -1}, {26, 43, -1}, {26, 45, 1}, {26, 47, -1}, {26, 49, 1}, {26, 51, -1}, {26, 53, -1}, {26, 55, 1}, {26, 57, -1}, {26, 59, 1}, {27, 1, 1}, {27, 3, 0}, {27, 5, -1}, {27, 7, -1}, {27, 9, 0}, {27, 11, 1}, {27, 13, 1}, {27, 15, 0}, {27, 17, -1}, {27, 19, -1}, {27, 21, 0}, {27, 23, 1}, {27, 25, 1}, {27, 27, 0}, {27, 29, -1}, {27, 31, -1}, {27, 33, 0}, {27, 35, 1}, {27, 37, 1}, {27, 39, 0}, {27, 41, -1}, {27, 43, -1}, {27, 45, 0}, {27, 47, 1}, {27, 49, 1}, {27, 51, 0}, {27, 53, -1}, {27, 55, -1}, {27, 57, 0}, {27, 59, 1}, {28, 1, 1}, {28, 3, 1}, {28, 5, -1}, {28, 7, 0}, {28, 9, 1}, {28, 11, -1}, {28, 13, -1}, {28, 15, -1}, {28, 17, -1}, {28, 19, 1}, {28, 21, 0}, {28, 23, -1}, {28, 25, 1}, {28, 27, 1}, {28, 29, 1}, {28, 31, 1}, {28, 33, -1}, {28, 35, 0}, {28, 37, 1}, {28, 39, -1}, {28, 41, -1}, {28, 43, -1}, {28, 45, -1}, {28, 47, 1}, {28, 49, 0}, {28, 51, -1}, {28, 53, 1}, {28, 55, 1}, {28, 57, 1}, {28, 59, 1}, {29, 1, 1}, {29, 3, -1}, {29, 5, 1}, {29, 7, 1}, {29, 9, 1}, {29, 11, -1}, {29, 13, 1}, {29, 15, -1}, {29, 17, -1}, {29, 19, -1}, {29, 21, -1}, {29, 23, 1}, {29, 25, 1}, {29, 27, -1}, {29, 29, 0}, {29, 31, -1}, {29, 33, 1}, {29, 35, 1}, {29, 37, -1}, {29, 39, -1}, {29, 41, -1}, {29, 43, -1}, {29, 45, 1}, {29, 47, -1}, {29, 49, 1}, {29, 51, 1}, {29, 53, 1}, {29, 55, -1}, {29, 57, 1}, {29, 59, 1}, {30, 1, 1}, {30, 3, 0}, {30, 5, 0}, {30, 7, 1}, {30, 9, 0}, {30, 11, -1}, {30, 13, 1}, {30, 15, 0}, {30, 17, 1}, {30, 19, 1}, {30, 21, 0}, {30, 23, -1}, {30, 25, 0}, {30, 27, 0}, {30, 29, 1}, {30, 31, -1}, {30, 33, 0}, {30, 35, 0}, {30, 37, 1}, {30, 39, 0}, {30, 41, -1}, {30, 43, -1}, {30, 45, 0}, {30, 47, -1}, {30, 49, 1}, {30, 51, 0}, {30, 53, -1}, {30, 55, 0}, {30, 57, 0}, {30, 59, -1}, {1001, 9907, -1} }; #if defined(GOO_HAS_CRYPTO) #include #elif !defined(_WIN32) #include #include #include #ifndef O_CLOEXEC #define O_CLOEXEC 0 #endif #endif static int get_entropy(void *dst, size_t len) { #if defined(GOO_HAS_CRYPTO) for (;;) { int status = RAND_status(); ASSERT(status >= 0); if (status != 0) break; if (RAND_poll() == 0) break; } return RAND_bytes((unsigned char *)dst, (int)len) == 1; #elif !defined(_WIN32) char *ptr = (char *)dst; size_t left = len; int fd = open("/dev/urandom", O_RDONLY | O_CLOEXEC); if (fd == -1) { fd = open("/dev/random", O_RDONLY | O_CLOEXEC); if (fd == -1) return 0; } while (left > 0) { int bytes = read(fd, ptr, left); if (bytes <= 0) { close(fd); return 0; } ASSERT((size_t)bytes <= left); left -= bytes; ptr += bytes; } ASSERT(left == 0); ASSERT(ptr == (char *)dst + len); close(fd); return 1; #else return 0; #endif } static void rng_init(goo_prng_t *rng) { unsigned char entropy[32]; if (!get_entropy(entropy, sizeof(entropy))) { size_t i; for (i = 0; i < sizeof(entropy); i++) entropy[i] = (unsigned char)rand(); printf("Warning: using bad entropy.\n"); } goo_prng_init(rng); goo_prng_seed(rng, entropy, GOO_PRNG_LOCAL); } static void rng_clear(goo_prng_t *rng) { goo_prng_uninit(rng); } static void random_prime(mpz_t ret, goo_prng_t *rng, size_t bits) { unsigned char key[32]; do { goo_prng_random_bits(rng, ret, bits); goo_prng_generate(rng, key, sizeof(key)); } while (!goo_is_prime(ret, key)); } static void run_hash_test(void) { static const char msg[] = "hello world"; unsigned char out[32]; static const unsigned char expect1[] = { 0xb9, 0x4d, 0x27, 0xb9, 0x93, 0x4d, 0x3e, 0x08, 0xa5, 0x2e, 0x52, 0xd7, 0xda, 0x7d, 0xab, 0xfa, 0xc4, 0x84, 0xef, 0xe3, 0x7a, 0x53, 0x80, 0xee, 0x90, 0x88, 0xf7, 0xac, 0xe2, 0xef, 0xcd, 0xe9 }; static const unsigned char expect2[] = { 0x4f, 0x18, 0xbc, 0xc1, 0x3c, 0x4b, 0x6e, 0x96, 0xd0, 0x86, 0xdf, 0xd7, 0x08, 0x1d, 0x02, 0xcb, 0xeb, 0xca, 0xbe, 0xe7, 0x78, 0xb1, 0x03, 0xfa, 0x3a, 0x84, 0x4b, 0x00, 0x0c, 0xeb, 0xd0, 0xfe }; goo_sha256_t ctx; unsigned long i; printf("Testing hashing...\n"); goo_sha256_init(&ctx); goo_sha256_update(&ctx, (unsigned char *)msg, sizeof(msg) - 1); goo_sha256_final(&ctx, out); ASSERT(memcmp(out, expect1, sizeof(out)) == 0); for (i = 0; i < 1000; i++) goo_sha256(out, out, sizeof(out)); ASSERT(memcmp(out, expect2, sizeof(out)) == 0); goo_sha256_init(&ctx); goo_sha256_update(&ctx, GOO_AOL1, sizeof(GOO_AOL1)); goo_sha256_final(&ctx, out); ASSERT(memcmp(out, GOO_AOL1_HASH, sizeof(out)) == 0); goo_sha256_init(&ctx); goo_sha256_update(&ctx, GOO_AOL2, sizeof(GOO_AOL2)); goo_sha256_final(&ctx, out); ASSERT(memcmp(out, GOO_AOL2_HASH, sizeof(out)) == 0); goo_sha256_init(&ctx); goo_sha256_update(&ctx, GOO_RSA2048, sizeof(GOO_RSA2048)); goo_sha256_final(&ctx, out); ASSERT(memcmp(out, GOO_RSA2048_HASH, sizeof(out)) == 0); goo_sha256_init(&ctx); goo_sha256_update(&ctx, GOO_RSA617, sizeof(GOO_RSA617)); goo_sha256_final(&ctx, out); ASSERT(memcmp(out, GOO_RSA617_HASH, sizeof(out)) == 0); } static void run_hmac_test(void) { static const char msg[] = "hello world"; unsigned char key[32]; unsigned char out[32]; static const unsigned char expect1[] = { 0x42, 0xeb, 0x78, 0x77, 0x6a, 0xd8, 0x2f, 0x00, 0x11, 0x79, 0xf4, 0x4e, 0x9e, 0x88, 0x26, 0x4f, 0x2d, 0x80, 0x42, 0x51, 0xe0, 0x2d, 0x98, 0x8c, 0x11, 0x94, 0xb9, 0x5d, 0xe8, 0x23, 0xa1, 0x4e }; static const unsigned char expect2[] = { 0x61, 0x7a, 0xec, 0xf0, 0x88, 0x8c, 0x86, 0x8c, 0x58, 0x8d, 0x16, 0x68, 0xf3, 0x4b, 0x59, 0x35, 0xe6, 0x68, 0x5d, 0x87, 0xed, 0xf9, 0xdb, 0xa4, 0x9d, 0x8c, 0x83, 0x08, 0x83, 0xa2, 0xeb, 0x18 }; goo_hmac_t ctx; unsigned long i; memset(key, 0xff, sizeof(key)); printf("Testing HMAC...\n"); goo_hmac_init(&ctx, key, sizeof(key)); goo_hmac_update(&ctx, (unsigned char *)msg, sizeof(msg) - 1); goo_hmac_final(&ctx, out); ASSERT(memcmp(out, expect1, sizeof(out)) == 0); for (i = 0; i < 1000; i++) { memset(key, i & 0xff, sizeof(key)); goo_hmac(out, out, sizeof(out), key, sizeof(key)); } ASSERT(memcmp(out, expect2, sizeof(out)) == 0); } static void run_drbg_test(void) { static const unsigned char expect1[] = { 0x40, 0xe9, 0x5c, 0x4d, 0xba, 0x22, 0xfd, 0x05, 0xd1, 0x57, 0x84, 0x07, 0x5b, 0x05, 0xca, 0x7c, 0x0b, 0x06, 0x3a, 0x43, 0xdc, 0xec, 0x33, 0x07, 0x12, 0x25, 0x75, 0xa7, 0xb5, 0xe3, 0x2d, 0x3b }; static const unsigned char expect2[] = { 0x4d, 0x06, 0x56, 0x62, 0xaf, 0xc2, 0x92, 0x7a, 0x34, 0x26, 0xc1, 0x2d, 0xd1, 0xc3, 0x52, 0x62 }; static const unsigned char expect3[] = { 0x70, 0x51, 0x19, 0xfd, 0x15, 0x36, 0xe2, 0xa7, 0xec, 0x80, 0x4d, 0xb4, 0x9f, 0x82, 0x62, 0xce }; static const unsigned char expect4[] = { 0xa5, 0x60, 0x40, 0xc8, 0x24, 0xe8, 0x8a, 0x5b, 0xac, 0x52, 0x93, 0x1e, 0xc0, 0x39, 0xcb, 0x41, 0xfa, 0xd8, 0x91, 0x33, 0xdd, 0x78, 0x95, 0x90, 0x5e, 0xf6, 0xf7, 0x58, 0x9e, 0xa2, 0x62, 0xc1 }; unsigned char entropy[64]; unsigned char out[36]; goo_drbg_t ctx; unsigned long i; memset(entropy, 0xaa, 64); printf("Testing DRBG...\n"); goo_drbg_init(&ctx, entropy, 64); goo_drbg_generate(&ctx, out, 32); ASSERT(memcmp(out, expect1, 32) == 0); goo_drbg_generate(&ctx, out, 16); ASSERT(memcmp(out, expect2, 16) == 0); goo_drbg_generate(&ctx, out, 16); ASSERT(memcmp(out, expect3, 16) == 0); memset(&entropy[0], 0x01, 32); memset(&entropy[32], 0x02, 32); goo_drbg_init(&ctx, entropy, 64); for (i = 0; i < 1000; i++) goo_drbg_generate(&ctx, out, ((i + 1) * 32) % 37); goo_drbg_generate(&ctx, out, 32); ASSERT(memcmp(out, expect4, 32) == 0); } static void run_prng_test(void) { const unsigned char expect[] = { 0xe9, 0x39, 0x0c, 0x3b, 0x67, 0x69, 0x24, 0x42, 0x76, 0xcf, 0x4f, 0xfa, 0x00, 0xff, 0x50, 0x53, 0x78, 0x91, 0xed, 0x2d, 0x78, 0xe3, 0xb0, 0xbb, 0x02, 0xd5, 0xfb, 0xb2, 0xab, 0x49, 0xbf, 0xf7 }; goo_prng_t prng; unsigned char key[32]; unsigned char s_prime[32]; unsigned char msg[32]; unsigned char slab[GOO_MAX_RSA_BYTES]; mpz_t x, y; unsigned long i; printf("Testing PRNG...\n"); memset(key, 0xaa, sizeof(key)); goo_prng_init(&prng); mpz_init(x); mpz_init(y); goo_prng_seed(&prng, key, GOO_PRNG_DERIVE); goo_prng_random_bits(&prng, x, 256); ASSERT(mpz_sgn(x) > 0); ASSERT(goo_mpz_bitlen(x) <= 256); goo_prng_random_int(&prng, y, x); ASSERT(mpz_sgn(y) > 0); ASSERT(goo_mpz_bitlen(y) <= 256); ASSERT(mpz_cmp(y, x) < 0); goo_prng_random_bits(&prng, x, 30); ASSERT(mpz_cmp_ui(x, 297763732) == 0); goo_prng_random_bits(&prng, x, 31); ASSERT(mpz_cmp_ui(x, 2131273610) == 0); goo_prng_random_bits(&prng, x, 31); goo_prng_random_int(&prng, y, x); ASSERT(mpz_cmp_ui(y, 670061897) == 0); ASSERT(goo_prng_random_num(&prng, 65537) == 41044); goo_prng_random_bits(&prng, x, 1024); goo_prng_random_bits(&prng, y, 1024); goo_prng_generate(&prng, s_prime, sizeof(s_prime)); goo_prng_generate(&prng, msg, sizeof(msg)); goo_prng_seed_sign(&prng, x, y, s_prime, msg, sizeof(msg), slab); goo_prng_random_bits(&prng, x, 31); ASSERT(mpz_cmp_ui(x, 1886980239) == 0); memset(key, 0x01, sizeof(key)); goo_prng_seed(&prng, key, GOO_PRNG_DERIVE); for (i = 0; i < 1000; i++) goo_prng_random_bits(&prng, x, ((i + 1) * 512) % 521); goo_prng_random_bits(&prng, x, 256); goo_mpz_import(y, expect, sizeof(expect)); ASSERT(mpz_cmp(x, y) == 0); mpz_clear(x); mpz_clear(y); goo_prng_uninit(&prng); } #ifdef GOO_HAS_CRYPTO #include static void run_sha256_test(goo_prng_t *rng) { unsigned char msg[2048]; unsigned char out[32]; unsigned char expect[32]; unsigned long i; printf("Testing SHA256...\n"); for (i = 0; i < 2048; i++) { size_t msg_len = (size_t)goo_prng_random_num(rng, 2048); goo_prng_generate(rng, msg, msg_len); goo_sha256(out, msg, msg_len); SHA256(msg, msg_len, expect); ASSERT(memcmp(out, expect, sizeof(out)) == 0); /* test chunks */ { size_t chunk_max = msg_len >> 2; size_t pos = 0; goo_sha256_t ctx; if (chunk_max < 2) chunk_max = 2; goo_sha256_init(&ctx); while (pos < msg_len) { size_t chunk_len = goo_prng_random_num(rng, chunk_max); if (pos + chunk_len > msg_len) chunk_len = msg_len - pos; goo_sha256_update(&ctx, &msg[pos], chunk_len); pos += chunk_len; } goo_sha256_final(&ctx, out); ASSERT(memcmp(out, expect, sizeof(out)) == 0); } } } #endif static void run_util_test(goo_prng_t *rng) { /* test bitlen and zerobits */ { mpz_t n; printf("Testing bitlen & zerobits...\n"); mpz_init(n); mpz_set_ui(n, 0x010001); ASSERT(goo_mpz_zerobits(n) == 0); ASSERT(goo_mpz_bitlen(n) == 17); mpz_set_si(n, -0x010001); ASSERT(goo_mpz_zerobits(n) == 0); ASSERT(goo_mpz_bitlen(n) == 17); mpz_set_ui(n, 0x20000); ASSERT(goo_mpz_zerobits(n) == 17); ASSERT(goo_mpz_bitlen(n) == 18); mpz_set_si(n, -0x20000); ASSERT(goo_mpz_zerobits(n) == 17); ASSERT(goo_mpz_bitlen(n) == 18); mpz_clear(n); } /* test mask */ { mpz_t n, t; printf("Testing mask...\n"); mpz_init(n); mpz_init(t); mpz_set_ui(n, 0xffff1234); goo_mpz_mask(n, n, 16, t); ASSERT(mpz_cmp_ui(n, 0x1234) == 0); mpz_clear(n); mpz_clear(t); } /* test sqrt */ { unsigned long i; printf("Testing sqrt...\n"); ASSERT(goo_isqrt(0) == 0); ASSERT(goo_isqrt(1) == 1); ASSERT(goo_isqrt(2) == 1); ASSERT(goo_isqrt(3) == 1); ASSERT(goo_isqrt(4) == 2); ASSERT(goo_isqrt(1024) == 32); ASSERT(goo_isqrt(1025) == 32); for (i = 0; i < 1000; i++) { uint32_t n = goo_prng_random_num(rng, 0x10000ul); ASSERT(goo_isqrt(n * n) == n); } } /* test sqrts */ { mpz_t p, q, n; printf("Testing roots...\n"); mpz_init(p); mpz_init(q); mpz_init(n); goo_mpz_import(p, PRIME_P_2048, sizeof(PRIME_P_2048)); goo_mpz_import(q, PRIME_Q_2048, sizeof(PRIME_Q_2048)); goo_mpz_import(n, MODULUS_4096, sizeof(MODULUS_4096)); /* test sqrtm */ { mpz_t x, y; printf("Testing sqrtm...\n"); mpz_init(x); mpz_init(y); goo_prng_random_int(rng, x, p); mpz_powm_ui(x, x, 2, p); if (mpz_sgn(x) != 0) ASSERT(mpz_jacobi(x, p) == 1); ASSERT(goo_mpz_sqrtm(y, x, p)); mpz_powm_ui(y, y, 2, p); ASSERT(mpz_cmp(y, x) == 0); mpz_clear(x); mpz_clear(y); } /* test sqrtpq */ { mpz_t x, y; printf("Testing sqrtpq...\n"); mpz_init(x); mpz_init(y); goo_prng_random_int(rng, x, n); mpz_powm_ui(x, x, 2, n); ASSERT(goo_mpz_sqrtpq(y, x, p, q)); mpz_powm_ui(y, y, 2, n); ASSERT(mpz_cmp(y, x) == 0); mpz_clear(x); mpz_clear(y); } mpz_clear(p); mpz_clear(q); mpz_clear(n); } /* test sqrts */ { mpz_t p, q, n; unsigned long i; printf("Testing roots (random)...\n"); mpz_init(p); mpz_init(q); mpz_init(n); for (i = 0; i < 20; i++) { random_prime(p, rng, 256); random_prime(q, rng, 256); mpz_mul(n, p, q); /* test sqrtm */ { mpz_t x, y; mpz_init(x); mpz_init(y); goo_prng_random_int(rng, x, p); mpz_powm_ui(x, x, 2, p); if (mpz_sgn(x) != 0) { ASSERT(mpz_jacobi(x, p) == 1); if ((mpz_getlimbn(p, 0) & 3) == 3) { mpz_sub(y, p, x); ASSERT(mpz_jacobi(y, p) == -1); } } ASSERT(goo_mpz_sqrtm(y, x, p)); mpz_powm_ui(y, y, 2, p); ASSERT(mpz_cmp(y, x) == 0); mpz_clear(x); mpz_clear(y); } /* test sqrtpq */ { mpz_t x, y; mpz_init(x); mpz_init(y); goo_prng_random_int(rng, x, n); mpz_powm_ui(x, x, 2, n); ASSERT(goo_mpz_sqrtpq(y, x, p, q)); mpz_powm_ui(y, y, 2, n); ASSERT(mpz_cmp(y, x) == 0); mpz_clear(x); mpz_clear(y); } } mpz_clear(p); mpz_clear(q); mpz_clear(n); } /* test jacobi */ { size_t i; printf("Testing jacobi...\n"); ASSERT(GOO_ARRAY_SIZE(SYMBOLS) > 0); for (i = 0; i < GOO_ARRAY_SIZE(SYMBOLS); i++) { const int *v = SYMBOLS[i]; mpz_t x, y; mpz_init(x); mpz_init(y); mpz_set_si(x, v[0]); mpz_set_si(y, v[1]); ASSERT(mpz_jacobi(x, y) == v[2]); mpz_clear(x); mpz_clear(y); } } } static void run_primes_test(goo_prng_t *rng) { /* https://github.com/golang/go/blob/aadaec5/src/math/big/prime_test.go */ static const char *primes[] = { "2", "3", "5", "7", "11", "13756265695458089029", "13496181268022124907", "10953742525620032441", "17908251027575790097", /* https://golang.org/issue/638 */ "18699199384836356663", "98920366548084643601728869055592650835572950" "932266967461790948584315647051443", "94560208308847015747498523884063394671606671" "904944666360068158221458669711639", /* https://primes.utm.edu/lists/small/small3.html */ "44941799905544149399470929709310851301537378" "70495584992054923478717299275731182628115083" "86655998299074566974373711472560655026288668" "09429169935784346436300314467494034591243112" "9144354948751003607115263071543163", "23097585999320415066642353898855783955556024" "39290654154349809042583105307530067238571397" "42334640122533598517597674807096648905501653" "46168760133978281431612497154796891289321400" "2992086353183070342498989426570593", "55217120996659062215404232070193333791252654" "62121169655563495403888449493493629943498064" "60453696177511076537774555037706789360724602" "06949729597808391514524577288553821135558677" "43022746090187341871655890805971735385789993", "20395687835640197740576586692903457728019399" "33143482630947726464532830627227012776329366" "16063144088173312372882677123879538709400158" "30656733832827915449969836607190676644003707" "42171178056908727928481491120222863321448761" "83376326512083574821647933992961249917319836" "219304274280243803104015000563790123", /* ECC primes: https://tools.ietf.org/html/draft-ladd-safecurves-02 */ /* Curve1174: 2^251-9 */ "36185027886661311069865932815214971204146870" "20801267626233049500247285301239", /* Curve25519: 2^255-19 */ "57896044618658097711785492504343953926634992" "332820282019728792003956564819949", /* E-382: 2^382-105 */ "98505015490986198030697600250359034512699348" "17616361666987073351061430442874302652853566" "563721228910201656997576599", /* Curve41417: 2^414-17 */ "42307582002575910332922579714097346549017899" "70971399803421752289756197063912392613281210" "9468141778230245837569601494931472367", /* E-521: 2^521-1 */ "68647976601306097149819007990813932172694353" "00143305409394463459185543183397656052122559" "64066145455497729631139148085803712198799971" "6643812574028291115057151", /* P-112 */ "4451685225093714772084598273548427", /* P-192 */ "62771017353866807638357894232076664160839087" "00390324961279", /* P-224 */ "26959946667150639794667015087019630673557916" "260026308143510066298881", /* P-256 */ "11579208921035624876269744694940757353008614" "3415290314195533631308867097853951", /* P-384 */ "39402006196394479212279040100143613805079739" "27046544666794829340424572177149687032904726" "6088258938001861606973112319", /* K-256 */ "11579208923731619542357098500868790785326998" "4665640564039457584007908834671663", /* K-256 Order */ "11579208923731619542357098500868790785283756" "4279074904382605163141518161494337", /* P-448 */ "72683872429560689054932380788800453435364136" "06873180602814901991806123281667307726863963" "83698676545930088884461843637361053498018365" "439" }; static const char *composites[] = { "0", "1", "2128417509121468791277119989830729774821167291" "4763848041968395774954376176754", "6084766654921918907427900243509372380954290099" "172559290432744450051395395951", "8459435049322191838921335299203232428036771124" "7940675652888030554255915464401", "82793403787388584738507275144194252681", /* Arnault, "Rabin-Miller Primality Test: Composite Numbers Which Pass It", */ /* Mathematics of Computation, 64(209) (January 1995), pp. 335-361. */ /* Strong pseudoprime to prime bases 2 through 29. */ "1195068768795265792518361315725116351898245581", /* Strong pseudoprime to all prime bases up to 200. */ "8038374574536394912570796143419421081388376882" "8755814583748891752229742737653336521865023361" "6396004545791504202360320876656996676098728404" "3965408232928738791850869166857328267761771029" "3896977394701670823042868710999743997654414484" "5341155872450633409279022275296229414984230688" "1685404326457534018329786111298960644845216191" "652872597534901", /* Extra-strong Lucas pseudoprimes. */ /* https://oeis.org/A217719 */ "989", "3239", "5777", "10877", "27971", "29681", "30739", "31631", "39059", "72389", "73919", "75077", "100127", "113573", "125249", "137549", "137801", "153931", "155819", "161027", "162133", "189419", "218321", "231703", "249331", "370229", "429479", "430127", "459191", "473891", "480689", "600059", "621781", "632249", "635627", "3673744903", "3281593591", "2385076987", "2738053141", "2009621503", "1502682721", "255866131", "117987841", "587861", "6368689", "8725753", "80579735209", "105919633" }; static const unsigned long mr_pseudos[] = { /* https://oeis.org/A001262 */ 2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751 }; static const unsigned long lucas_pseudos[] = { /* https://oeis.org/A217719 */ 989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, 72389, 73919, 75077 }; unsigned char key[32]; unsigned char zero[32]; unsigned long i; goo_prng_generate(rng, key, sizeof(key)); memset(zero, 0x00, sizeof(zero)); printf("Testing primes...\n"); ASSERT(GOO_ARRAY_SIZE(primes) > 0); for (i = 0; i < GOO_ARRAY_SIZE(primes); i++) { mpz_t p; mpz_init(p); ASSERT(mpz_set_str(p, primes[i], 10) == 0); ASSERT(goo_is_prime_div(p)); ASSERT(goo_is_prime_mr(p, key, 16 + 1, 1)); ASSERT(goo_is_prime_mr(p, key, 1, 1)); ASSERT(goo_is_prime_mr(p, key, 1, 0)); ASSERT(goo_is_prime_mr(p, key, 0, 1)); ASSERT(goo_is_prime_lucas(p, 50)); ASSERT(goo_is_prime(p, key)); mpz_clear(p); } for (i = 0; i < GOO_ARRAY_SIZE(goo_primes); i++) { mpz_t p; mpz_init(p); mpz_set_ui(p, goo_primes[i]); ASSERT(goo_is_prime_div(p) == 1); ASSERT(goo_is_prime_mr(p, key, 16 + 1, 1)); ASSERT(goo_is_prime_mr(p, key, 1, 1)); ASSERT(goo_is_prime_mr(p, key, 1, 0)); ASSERT(goo_is_prime_mr(p, key, 0, 1)); ASSERT(goo_is_prime_lucas(p, 50)); ASSERT(goo_is_prime(p, key)); mpz_clear(p); } for (i = 0; i < GOO_ARRAY_SIZE(goo_test_primes); i++) { mpz_t p; mpz_init(p); mpz_set_ui(p, goo_test_primes[i]); ASSERT(goo_is_prime_div(p) == 1); ASSERT(goo_is_prime_mr(p, key, 16 + 1, 1)); ASSERT(goo_is_prime_mr(p, key, 1, 1)); ASSERT(goo_is_prime_mr(p, key, 1, 0)); ASSERT(goo_is_prime_mr(p, key, 0, 1)); ASSERT(goo_is_prime_lucas(p, 50)); ASSERT(goo_is_prime(p, key)); mpz_clear(p); } printf("Testing composites...\n"); ASSERT(GOO_ARRAY_SIZE(composites) > 0); for (i = 0; i < GOO_ARRAY_SIZE(composites); i++) { mpz_t p; mpz_init(p); ASSERT(mpz_set_str(p, composites[i], 10) == 0); if (i == 6 || i == 7 || (i >= 43 && i <= 49) || i == 54) { ASSERT(goo_is_prime_div(p)); } else { /* We actually catch a surpising */ /* number of composites here. */ ASSERT(!goo_is_prime_div(p)); } /* MR with a deterministic key. */ ASSERT(!goo_is_prime_mr(p, zero, 16 + 1, 1)); ASSERT(!goo_is_prime_mr(p, zero, 4, 1)); ASSERT(!goo_is_prime_mr(p, zero, 4, 0)); if (i >= 8 && i <= 42) { /* Lucas pseudoprime. */ ASSERT(goo_is_prime_lucas(p, 50)); } else { ASSERT(!goo_is_prime_lucas(p, 50)); } /* No composite should ever pass */ /* Baillie-PSW, random or otherwise. */ ASSERT(!goo_is_prime(p, zero)); ASSERT(!goo_is_prime(p, key)); mpz_clear(p); } printf("Testing miller-rabin pseudo-primes...\n"); { const unsigned long *want = mr_pseudos; size_t len = GOO_ARRAY_SIZE(mr_pseudos); mpz_t n; mpz_init(n); ASSERT(len > 0); for (i = 3; i < 100000; i += 2) { int pseudo; mpz_set_ui(n, i); pseudo = goo_is_prime_mr(n, zero, 1, 1) && !goo_is_prime_lucas(n, 50); if (pseudo && (len == 0 || i != want[0])) ASSERT(0 && "miller-rabin: want false"); else if (!pseudo && len >= 1 && i == want[0]) ASSERT(0 && "miller-rabin: want true"); if (len > 0 && i == want[0]) { want++; len--; } } ASSERT(len == 0); mpz_clear(n); } printf("Testing lucas pseudo-primes...\n"); { const unsigned long *want = lucas_pseudos; size_t len = GOO_ARRAY_SIZE(lucas_pseudos); mpz_t n; mpz_init(n); ASSERT(len > 0); for (i = 3; i < 100000; i += 2) { int pseudo; mpz_set_ui(n, i); pseudo = goo_is_prime_lucas(n, 50) && !goo_is_prime_mr(n, zero, 1, 1); if (pseudo && (len == 0 || i != want[0])) ASSERT(0 && "lucas: want false"); else if (!pseudo && len >= 1 && i == want[0]) ASSERT(0 && "lucas: want true"); if (len > 0 && i == want[0]) { want++; len--; } } ASSERT(len == 0); mpz_clear(n); } /* test next_prime */ { mpz_t n; printf("Testing next_prime (1)...\n"); mpz_init(n); mpz_set_ui(n, 4); ASSERT(goo_next_prime(n, n, zero, 512)); ASSERT(mpz_cmp_ui(n, 5) == 0); mpz_clear(n); } /* test next_prime */ { mpz_t n, e, r; printf("Testing next_prime (2)...\n"); mpz_init(n); mpz_init(e); mpz_init(r); goo_mpz_import(n, PRIME_P_1024, sizeof(PRIME_P_1024)); mpz_add_ui(n, n, 1); mpz_add_ui(e, n, 885); ASSERT(!goo_next_prime(r, n, zero, 884)); ASSERT(goo_next_prime(r, n, zero, 885)); ASSERT(mpz_cmp(r, e) == 0); mpz_clear(n); mpz_clear(e); mpz_clear(r); } } static void run_ops_test(goo_prng_t *rng) { mpz_t n; goo_group_t *goo; printf("Testing group ops...\n"); mpz_init(n); goo_mpz_import(n, GOO_RSA2048, sizeof(GOO_RSA2048)); goo = goo_malloc(sizeof(goo_group_t)); ASSERT(goo_group_init(goo, n, 2, 3, 2048)); { printf("Testing comb calculation...\n"); ASSERT(goo->combs[0].g.points_per_add == 8); ASSERT(goo->combs[0].g.adds_per_shift == 2); ASSERT(goo->combs[0].g.shifts == 128); ASSERT(goo->combs[0].g.bits_per_window == 256); ASSERT(goo->combs[0].g.bits == 2048); ASSERT(goo->combs[0].g.points_per_subcomb == 255); ASSERT(goo->combs[0].g.size == 510); ASSERT(goo->combs[0].h.points_per_add == 8); ASSERT(goo->combs[0].h.adds_per_shift == 2); ASSERT(goo->combs[0].h.shifts == 128); ASSERT(goo->combs[0].h.bits_per_window == 256); ASSERT(goo->combs[0].h.bits == 2048); ASSERT(goo->combs[0].h.points_per_subcomb == 255); ASSERT(goo->combs[0].h.size == 510); ASSERT(goo->combs[1].g.points_per_add == 8); ASSERT(goo->combs[1].g.adds_per_shift == 2); ASSERT(goo->combs[1].g.shifts == 265); ASSERT(goo->combs[1].g.bits_per_window == 530); ASSERT(goo->combs[1].g.bits == 4240); ASSERT(goo->combs[1].g.points_per_subcomb == 255); ASSERT(goo->combs[1].g.size == 510); ASSERT(goo->combs[1].h.points_per_add == 8); ASSERT(goo->combs[1].h.adds_per_shift == 2); ASSERT(goo->combs[1].h.shifts == 265); ASSERT(goo->combs[1].h.bits_per_window == 530); ASSERT(goo->combs[1].h.bits == 4240); ASSERT(goo->combs[1].h.points_per_subcomb == 255); ASSERT(goo->combs[1].h.size == 510); } /* test pow */ { mpz_t b, bi, e; mpz_t r1, r2; unsigned long i; printf("Testing pow...\n"); mpz_init(b); mpz_init(bi); mpz_init(e); mpz_init(r1); mpz_init(r2); for (i = 0; i < 20; i++) { goo_prng_random_bits(rng, b, 2048); goo_prng_random_bits(rng, e, 4096); ASSERT(goo_group_inv(goo, bi, b)); ASSERT(goo_group_pow_slow(goo, r1, b, e)); ASSERT(goo_group_pow(goo, r2, b, bi, e)); ASSERT(mpz_cmp(r1, r2) == 0); } mpz_clear(b); mpz_clear(bi); mpz_clear(e); mpz_clear(r1); mpz_clear(r2); } /* test pow2 */ { mpz_t b1, b2, e1, e2; mpz_t b1i, b2i; mpz_t r1, r2; unsigned long i; printf("Testing pow2...\n"); mpz_init(b1); mpz_init(b2); mpz_init(e1); mpz_init(e2); mpz_init(b1i); mpz_init(b2i); mpz_init(r1); mpz_init(r2); for (i = 0; i < 20; i++) { goo_prng_random_bits(rng, b1, 2048); goo_prng_random_bits(rng, b2, 2048); goo_prng_random_bits(rng, e1, 128); goo_prng_random_bits(rng, e2, 128); ASSERT(goo_group_inv2(goo, b1i, b2i, b1, b2)); ASSERT(goo_group_pow2_slow(goo, r1, b1, e1, b2, e2)); ASSERT(goo_group_pow2(goo, r2, b1, b1i, e1, b2, b2i, e2)); ASSERT(mpz_cmp(r1, r2) == 0); } mpz_clear(b1); mpz_clear(b2); mpz_clear(e1); mpz_clear(e2); mpz_clear(b1i); mpz_clear(b2i); mpz_clear(r1); mpz_clear(r2); } /* test powgh */ { mpz_t e1, e2; mpz_t r1, r2; unsigned long i; printf("Testing powgh...\n"); mpz_init(e1); mpz_init(e2); mpz_init(r1); mpz_init(r2); for (i = 0; i < 20; i++) { goo_prng_random_bits(rng, e1, 2048 + GOO_ELL_BITS + 2 - 1); goo_prng_random_bits(rng, e2, 2048 + GOO_ELL_BITS + 2 - 1); ASSERT(goo_group_powgh_slow(goo, r1, e1, e2)); ASSERT(goo_group_powgh(goo, r2, e1, e2)); ASSERT(mpz_cmp(r1, r2) == 0); } mpz_clear(e1); mpz_clear(e2); mpz_clear(r1); mpz_clear(r2); } /* test inv2 */ { mpz_t e1, e2; mpz_t e1_s, e2_s; mpz_t e1_si, e2_si; mpz_t r1, r2; unsigned long i; printf("Testing inv2...\n"); mpz_init(e1); mpz_init(e2); mpz_init(e1_s); mpz_init(e2_s); mpz_init(e1_si); mpz_init(e2_si); mpz_init(r1); mpz_init(r2); for (i = 0; i < 20; i++) { goo_prng_random_bits(rng, e1, 2048); goo_prng_random_bits(rng, e2, 2048); mpz_fdiv_q_2exp(e1_s, e1, 1536); mpz_fdiv_q_2exp(e2_s, e2, 1536); ASSERT(goo_group_inv2(goo, e1_si, e2_si, e1_s, e2_s)); mpz_mul(r1, e1_s, e1_si); mpz_mod(r1, r1, goo->n); mpz_mul(r2, e2_s, e2_si); mpz_mod(r2, r1, goo->n); goo_group_reduce(goo, r1, r1); goo_group_reduce(goo, r2, r2); ASSERT(mpz_cmp_ui(r1, 1) == 0); ASSERT(mpz_cmp_ui(r2, 1) == 0); } mpz_clear(e1); mpz_clear(e2); mpz_clear(e1_s); mpz_clear(e2_s); mpz_clear(e1_si); mpz_clear(e2_si); mpz_clear(r1); mpz_clear(r2); } /* test inv7 */ { mpz_t evals[7]; mpz_t einvs[7]; unsigned long i, j; printf("Testing inv7...\n"); for (i = 0; i < 7; i++) { mpz_init(evals[i]); mpz_init(einvs[i]); } for (i = 0; i < 20; i++) { for (j = 0; j < 7; j++) goo_prng_random_bits(rng, evals[j], 2048); ASSERT(goo_group_inv7(goo, einvs[0], einvs[1], einvs[2], einvs[3], einvs[4], einvs[5], einvs[6], evals[0], evals[1], evals[2], evals[3], evals[4], evals[5], evals[6])); for (j = 0; j < 7; j++) { /* A 2^-2048 chance of happening by accident. */ ASSERT(mpz_cmp_ui(evals[j], 1) != 0); mpz_mul(evals[j], evals[j], einvs[j]); mpz_mod(evals[j], evals[j], goo->n); goo_group_reduce(goo, evals[j], evals[j]); ASSERT(mpz_cmp_ui(evals[j], 1) == 0); } } for (i = 0; i < 7; i++) { mpz_clear(evals[i]); mpz_clear(einvs[i]); } } mpz_clear(n); goo_group_uninit(goo); goo_free(goo); } static void run_combspec_test(void) { goo_combspec_t spec; long bits, points_per_subcomb; mpz_t n; goo_group_t *goo; printf("Testing combspec...\n"); ASSERT(goo_combspec_init(&spec, GOO_CHAL_BITS, GOO_MAX_COMB_SIZE)); bits = spec.bits_per_window * spec.points_per_add; points_per_subcomb = (1 << spec.points_per_add) - 1; ASSERT(spec.points_per_add == 8); ASSERT(spec.adds_per_shift == 2); ASSERT(spec.shifts == 8); ASSERT(spec.bits_per_window == 16); ASSERT(bits == 128); ASSERT(points_per_subcomb == 255); ASSERT(spec.size == 510); mpz_init(n); goo_mpz_import(n, GOO_RSA2048, sizeof(GOO_RSA2048)); goo = goo_malloc(sizeof(goo_group_t)); ASSERT(goo_group_init(goo, n, 2, 3, 0)); ASSERT(goo->combs[0].g.points_per_add == 7); ASSERT(goo->combs[0].g.adds_per_shift == 4); ASSERT(goo->combs[0].g.shifts == 5); ASSERT(goo->combs[0].g.bits_per_window == 20); ASSERT(goo->combs[0].g.bits == 140); ASSERT(goo->combs[0].g.points_per_subcomb == 127); ASSERT(goo->combs[0].g.size == 508); ASSERT(goo->combs[0].h.points_per_add == 7); ASSERT(goo->combs[0].h.adds_per_shift == 4); ASSERT(goo->combs[0].h.shifts == 5); ASSERT(goo->combs[0].h.bits_per_window == 20); ASSERT(goo->combs[0].h.bits == 140); ASSERT(goo->combs[0].h.points_per_subcomb == 127); ASSERT(goo->combs[0].h.size == 508); mpz_clear(n); goo_group_uninit(goo); goo_free(goo); } static void run_sig_test(void) { goo_sig_t sig1; goo_sig_t sig2; unsigned char *data = NULL; size_t size; printf("Testing signatures...\n"); goo_sig_init(&sig1); goo_sig_init(&sig2); mpz_set_ui(sig1.C2, 0x01); mpz_set_ui(sig1.t, 0x02); mpz_set_ui(sig1.chal, 0x03); mpz_set_ui(sig1.ell, 0x04); mpz_set_ui(sig1.Aq, 0x05); mpz_set_ui(sig1.Bq, 0x06); mpz_set_ui(sig1.Cq, 0x07); mpz_set_ui(sig1.Dq, 0x08); mpz_set_ui(sig1.Eq, 0x100); mpz_set_ui(sig1.z_w, 0x09); mpz_set_ui(sig1.z_w2, 0x0a); mpz_set_ui(sig1.z_s1, 0x0b); mpz_set_ui(sig1.z_a, 0x0c); mpz_set_ui(sig1.z_an, 0x0d); mpz_set_ui(sig1.z_s1w, 0x0e); mpz_set_ui(sig1.z_sa, 0x0f); size = goo_sig_size(&sig1, 2048); data = goo_malloc(size); ASSERT(goo_sig_export(data, &sig1, 2048)); ASSERT(goo_sig_import(&sig2, data, size, 2048)); ASSERT(mpz_cmp_ui(sig2.C2, 0x01) == 0); ASSERT(mpz_cmp_ui(sig2.t, 0x02) == 0); ASSERT(mpz_cmp_ui(sig2.chal, 0x03) == 0); ASSERT(mpz_cmp_ui(sig2.ell, 0x04) == 0); ASSERT(mpz_cmp_ui(sig2.Aq, 0x05) == 0); ASSERT(mpz_cmp_ui(sig2.Bq, 0x06) == 0); ASSERT(mpz_cmp_ui(sig2.Cq, 0x07) == 0); ASSERT(mpz_cmp_ui(sig2.Dq, 0x08) == 0); ASSERT(mpz_sgn(sig2.Eq) > 0); ASSERT(mpz_cmp_ui(sig2.Eq, 0x100) == 0); ASSERT(mpz_cmp_ui(sig2.z_w, 0x09) == 0); ASSERT(mpz_cmp_ui(sig2.z_w2, 0x0a) == 0); ASSERT(mpz_cmp_ui(sig2.z_s1, 0x0b) == 0); ASSERT(mpz_cmp_ui(sig2.z_a, 0x0c) == 0); ASSERT(mpz_cmp_ui(sig2.z_an, 0x0d) == 0); ASSERT(mpz_cmp_ui(sig2.z_s1w, 0x0e) == 0); ASSERT(mpz_cmp_ui(sig2.z_sa, 0x0f) == 0); mpz_set_si(sig1.Eq, -0x100); ASSERT(goo_sig_export(data, &sig1, 2048)); ASSERT(goo_sig_import(&sig2, data, size, 2048)); ASSERT(mpz_cmp_ui(sig2.C2, 0x01) == 0); ASSERT(mpz_cmp_ui(sig2.t, 0x02) == 0); ASSERT(mpz_cmp_ui(sig2.chal, 0x03) == 0); ASSERT(mpz_cmp_ui(sig2.ell, 0x04) == 0); ASSERT(mpz_cmp_ui(sig2.Aq, 0x05) == 0); ASSERT(mpz_cmp_ui(sig2.Bq, 0x06) == 0); ASSERT(mpz_cmp_ui(sig2.Cq, 0x07) == 0); ASSERT(mpz_cmp_ui(sig2.Dq, 0x08) == 0); ASSERT(mpz_sgn(sig2.Eq) < 0); ASSERT(mpz_cmp_si(sig2.Eq, -0x100) == 0); ASSERT(mpz_cmp_ui(sig2.z_w, 0x09) == 0); ASSERT(mpz_cmp_ui(sig2.z_w2, 0x0a) == 0); ASSERT(mpz_cmp_ui(sig2.z_s1, 0x0b) == 0); ASSERT(mpz_cmp_ui(sig2.z_a, 0x0c) == 0); ASSERT(mpz_cmp_ui(sig2.z_an, 0x0d) == 0); ASSERT(mpz_cmp_ui(sig2.z_s1w, 0x0e) == 0); ASSERT(mpz_cmp_ui(sig2.z_sa, 0x0f) == 0); goo_sig_uninit(&sig1); goo_sig_uninit(&sig2); goo_free(data); } static void run_goo_test(goo_prng_t *rng) { mpz_t p, q, n; mpz_t mod_n; mpz_t C1; goo_sig_t sig; goo_group_t *goo, *ver; unsigned char s_prime[32]; unsigned char msg[32]; unsigned long i; printf("Testing signing/verifying...\n"); mpz_init(p); mpz_init(q); mpz_init(n); mpz_init(mod_n); mpz_init(C1); goo_sig_init(&sig); goo = goo_malloc(sizeof(goo_group_t)); ver = goo_malloc(sizeof(goo_group_t)); goo_mpz_import(p, PRIME_P_2048, sizeof(PRIME_P_2048)); goo_mpz_import(q, PRIME_Q_2048, sizeof(PRIME_Q_2048)); goo_mpz_import(n, MODULUS_4096, sizeof(MODULUS_4096)); goo_mpz_import(mod_n, GOO_RSA2048, sizeof(GOO_RSA2048)); goo_prng_generate(rng, s_prime, sizeof(s_prime)); goo_prng_generate(rng, msg, sizeof(msg)); ASSERT(goo_group_init(goo, mod_n, 2, 3, 4096)); ASSERT(goo_group_init(ver, mod_n, 2, 3, 0)); ASSERT(goo_group_challenge(goo, C1, s_prime, n)); ASSERT(goo_group_validate(goo, s_prime, C1, p, q)); ASSERT(goo_group_sign(goo, &sig, msg, sizeof(msg), s_prime, p, q)); ASSERT(goo_group_verify(goo, msg, sizeof(msg), &sig, C1)); ASSERT(goo_group_verify(ver, msg, sizeof(msg), &sig, C1)); for (i = 0; i < 5; i++) { size_t prime_size = 1024 + goo_prng_random_num(rng, 1024); random_prime(p, rng, prime_size); random_prime(q, rng, prime_size); mpz_mul(n, p, q); goo_prng_generate(rng, s_prime, sizeof(s_prime)); goo_prng_generate(rng, msg, sizeof(msg)); ASSERT(goo_group_challenge(goo, C1, s_prime, n)); ASSERT(goo_group_validate(goo, s_prime, C1, p, q)); ASSERT(goo_group_sign(goo, &sig, msg, sizeof(msg), s_prime, p, q)); ASSERT(goo_group_verify(goo, msg, sizeof(msg), &sig, C1)); ASSERT(goo_group_verify(ver, msg, sizeof(msg), &sig, C1)); } mpz_clear(p); mpz_clear(q); mpz_clear(n); mpz_clear(mod_n); mpz_clear(C1); goo_sig_uninit(&sig); goo_group_uninit(goo); goo_group_uninit(ver); goo_free(goo); goo_free(ver); } static void run_api_test(goo_prng_t *rng) { unsigned char *C1, *sig, *ct, *pt; size_t ct_len, pt_len; size_t C1_len, sig_len; unsigned char entropy1[32]; unsigned char entropy2[32]; unsigned char entropy3[32]; unsigned char s_prime[32]; unsigned char msg[32]; unsigned char exp[3] = {0x01, 0x00, 0x01}; goo_group_t *goo, *ver; printf("Testing API...\n"); goo_prng_generate(rng, entropy1, sizeof(entropy1)); goo_prng_generate(rng, entropy2, sizeof(entropy2)); goo_prng_generate(rng, entropy3, sizeof(entropy3)); goo_prng_generate(rng, msg, sizeof(msg)); goo = goo_create(GOO_RSA2048, sizeof(GOO_RSA2048), 2, 3, 4096); ver = goo_create(GOO_RSA2048, sizeof(GOO_RSA2048), 2, 3, 0); ASSERT(goo != NULL); ASSERT(ver != NULL); ASSERT(goo_generate(goo, s_prime, entropy1)); ASSERT(goo_challenge(goo, &C1, &C1_len, s_prime, MODULUS_4096, sizeof(MODULUS_4096))); ASSERT(goo_encrypt(goo, &ct, &ct_len, C1, C1_len, MODULUS_4096, sizeof(MODULUS_4096), exp, sizeof(exp), NULL, 0, entropy2)); ASSERT(goo_decrypt(goo, &pt, &pt_len, ct, ct_len, PRIME_P_2048, sizeof(PRIME_P_2048), PRIME_Q_2048, sizeof(PRIME_Q_2048), exp, sizeof(exp), NULL, 0, entropy3)); ASSERT(pt_len == C1_len); ASSERT(memcmp(pt, C1, pt_len) == 0); ASSERT(goo_validate(goo, s_prime, C1, C1_len, PRIME_P_2048, sizeof(PRIME_P_2048), PRIME_Q_2048, sizeof(PRIME_Q_2048))); ASSERT(goo_sign(goo, &sig, &sig_len, msg, sizeof(msg), s_prime, PRIME_P_2048, sizeof(PRIME_P_2048), PRIME_Q_2048, sizeof(PRIME_Q_2048))); ASSERT(goo_verify(goo, msg, sizeof(msg), sig, sig_len, C1, C1_len)); ASSERT(goo_verify(ver, msg, sizeof(msg), sig, sig_len, C1, C1_len)); goo_free(C1); goo_free(ct); goo_free(pt); goo_free(sig); goo_destroy(goo); goo_destroy(ver); } int main(void) { goo_prng_t rng; (void)PRIME_Q_1024; (void)MODULUS_2048; rng_init(&rng); run_hash_test(); run_hmac_test(); run_drbg_test(); run_prng_test(); #ifdef GOO_HAS_CRYPTO run_sha256_test(&rng); #endif run_util_test(&rng); run_primes_test(&rng); run_ops_test(&rng); run_combspec_test(); run_sig_test(); run_goo_test(&rng); run_api_test(&rng); rng_clear(&rng); printf("All tests passed!\n"); return 0; }