Hi, OpenSSL might benefit implementing secret-sharing and related algorithms, maybe step-by-step. Attached is an implementation of share of private exponent calculation provided share of (p-1)(q-1). Well, it is demonstrated here without shares but still does not involve inverse unknown modulo. This code is based on Dan Boneh and Matthew Franklin's paper and many thanx for the good and smart trick. Please consider this as contribution, Vadim
/* Copyright (C) 2000 Vadim Fedukovich ([EMAIL PROTECTED]) All rights reserved No warranties HOWTO compute private RSA key while distributed keypair generation without trusted dealer; work-around calculating reverse unknown modulus. Technique implemented was originally described in paper by Dan Boneh and Matthew Franklin, available at http://crypto.stanford.edu/~dabo/abstracts/sharing.html This product includes cryptographic software written by Eric Young ([EMAIL PROTECTED]) This product includes software developed by the OpenSSL Project for use in the OpenSSL Toolkit. (http://www.openssl.org/) */ /* Aug 12, 2000: it just works. */ #include <stdio.h> #include <openssl/crypto.h> #include <openssl/pem.h> #include <openssl/err.h> // a fresh 512-bit-modulus keypair long akey_size = 317; unsigned char akey_der[]; RSA *getkey(unsigned char *ptr, unsigned long size); int main() { RSA *keys; BIGNUM *phi, *r1, *r2, *theta, *tbd, *reminder, *altd; BN_CTX *ctx1, *ctx2; OpenSSL_add_all_algorithms(); ERR_load_crypto_strings(); keys = getkey(akey_der, akey_size); /* just in case.. */ phi = BN_new(); r1 = BN_new(); r2 = BN_new(); ctx1 = BN_CTX_new(); ctx2 = BN_CTX_new(); theta = BN_new(); tbd = BN_new(); reminder = BN_new(); altd = BN_new(); /* Eric's code */ BN_sub(r1, keys->p, BN_value_one()); BN_sub(r2, keys->q, BN_value_one()); BN_mul(phi, r1, r2, ctx1); /* "Efficient Generation of Shared RSA keys", $6 */ theta = BN_mod_inverse(NULL, phi, keys->e, ctx2); BN_mul(tbd, theta, phi, ctx2); BN_sub_word(tbd, 1L); BN_div(altd, reminder, tbd, keys->e, ctx2); printf("Reminder: (zero expected)\n"); BN_print_fp(stdout, reminder); BN_sub(altd, phi, altd); printf("\nPrivate key just re-calculated: (should fit hardcoded_key->d)\n"); BN_print_fp(stdout, altd); printf("\nOriginal private key exponent:\n"); BN_print_fp(stdout, keys->d); printf("\n"); return 0; } RSA *getkey(unsigned char *ptr, unsigned long size) { unsigned char *p = ptr; RSA *it = d2i_RSAPrivateKey(NULL, &p, size); return it; } unsigned char akey_der[317]={ 0x30,0x82,0x01,0x39,0x02,0x01,0x00,0x02,0x41,0x00,0xBD,0x6F,0x51,0xB8,0xC9,0x58, 0x50,0x78,0x89,0x0D,0x2B,0x82,0xE7,0xDC,0x65,0xB8,0xEC,0x81,0xDB,0x59,0x58,0xF3, 0x15,0x7B,0x37,0x06,0x40,0x59,0x25,0x78,0xAD,0x58,0xD0,0x76,0x74,0xE8,0x0B,0xAE, 0x4F,0xC4,0xCC,0xC0,0xA1,0x7C,0x1D,0xCD,0xFB,0x47,0xB5,0x80,0x40,0x9D,0xC0,0x1E, 0x3A,0x03,0x17,0xE7,0xF4,0x33,0xF7,0x6A,0x3C,0x3B,0x02,0x03,0x01,0x00,0x01,0x02, 0x40,0x08,0xD6,0xD2,0xE7,0x5E,0x6D,0xC2,0x83,0x7D,0x51,0xA2,0x00,0x1F,0xB5,0x87, 0x01,0x93,0xF7,0x93,0x36,0x9E,0x11,0xE9,0xA4,0xB0,0x32,0x98,0x7A,0x10,0x67,0x8B, 0x1F,0x0F,0x1F,0xA3,0x17,0x44,0x9B,0x15,0x9C,0xA4,0x17,0xF6,0x16,0x28,0xA3,0x79, 0xEA,0x51,0xBC,0x5E,0xBB,0x1A,0x94,0xF5,0xFA,0x0A,0x24,0xE2,0x5B,0x43,0x58,0x62, 0x11,0x02,0x21,0x00,0xF5,0x2C,0x55,0xBD,0x9E,0x8E,0xAB,0x93,0x90,0xE6,0xB9,0x70, 0x85,0x37,0xAF,0x8B,0x3A,0x9B,0xF6,0xE9,0x08,0x86,0x5F,0xB9,0x30,0x23,0x53,0x7A, 0x91,0x36,0x89,0x4D,0x02,0x21,0x00,0xC5,0xCC,0xDD,0xCA,0xD9,0x6B,0xCD,0xBC,0xE5, 0x12,0x7B,0x8A,0x72,0x71,0x95,0x16,0x6B,0x43,0x59,0x52,0x28,0x9A,0x51,0x3F,0x58, 0xDF,0x8A,0xC7,0x52,0x23,0xD7,0xA7,0x02,0x20,0x66,0xF7,0x8B,0xBA,0xEB,0x50,0x77, 0xF6,0xAD,0xB0,0x78,0xC9,0x2C,0xE9,0xCA,0x2B,0xEB,0x1D,0x7D,0x81,0x39,0x37,0x56, 0x14,0x6C,0x87,0x29,0x94,0x1C,0x50,0x8F,0x31,0x02,0x20,0x5A,0xC3,0xC4,0x6E,0xC5, 0xD0,0x43,0x2B,0x4F,0xCE,0x68,0x64,0x42,0x59,0xBE,0x78,0xF8,0x25,0x82,0x82,0x41, 0xE1,0x76,0x30,0xE4,0x5E,0x47,0xB7,0x69,0x08,0xCB,0x77,0x02,0x20,0x5A,0xBA,0xB0, 0x52,0xB5,0x34,0x51,0xBB,0x83,0xE0,0x8C,0x82,0x1F,0xC0,0x5C,0x6D,0x27,0x32,0x66, 0x73,0x15,0x16,0x5B,0xAC,0x6C,0xE3,0x7D,0xB7,0x92,0x98,0x21,0xB1, };
