-1

I'd like to try to create a large prime number similar to what is created in OpenSSL but without extra libararies (ie. OpenSLL). Below this post there is a small sample code fromhttps://www.techiedelight.com/c-program-demonstrate-diffie-hellman-algorithm/. Let's say I've created a 128bit number. How would I modify the "compute" function to accommodate a 128bit number or larger?

#include <stdio.h>
 
// Function to compute `a^m mod n`
int compute(int a, int m, int n) {
    int r;
    int y = 1;
     while (m > 0)  {
        r = m % 2;
         // fast exponention
        if (r == 1) {
            y = (y*a) % n;
        }
        a = a*a % n;
        m = m / 2;
    }
     return y;
}
 
// C program to demonstrate the Diffie-Hellman algorithm
int main()
{
    int p = 23;        // modulus (prime number)
    int g = 5;        // base
    int a, b;    // `a` – Alice's secret key, `b` – Bob's secret key.
    int A, B;    // `A` – Alice's public key, `B` – Bob's public key
 
    // choose a secret integer for Alice's private key (only known to Alice)
    a = 6;        // or, use `rand()`
 
    // Calculate Alice's public key (Alice will send `A` to Bob)
    A = compute(g, a, p);
 
    // choose a secret integer for Bob's private key (only known to Bob)
    b = 15;        // or, use `rand()`
 
    // Calculate Bob's public key (Bob will send `B` to Alice)
    B = compute(g, b, p);
 
    // Alice and Bob Exchange their public key `A` and `B` with each other
 
    // Find secret key
    int keyA = compute(B, a, p);
    int keyB = compute(A, b, p);
 
    printf("Alice's secret key is %d\nBob's secret key is %d", keyA, keyB);
 
    return 0;
}
Maarten Bodewes
  • 84,836
  • 13
  • 136
  • 244
user1231247
  • 191
  • 1
  • 7
  • 1
    Maybe the Miller-Rabin test can help you: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test – byJavaDev May 27 '22 at 18:00
  • Your title is about creating a large prime but your text is about doing DH, i.e. modular exponentiation, which is entirely different. And you have tagged RSA, which is different from both of those. Also you should know 128-bit 'classical' (aka integer, Zp, modp, finite-field) DH is not secure at all; you need _at least_ about 1000 bits (1024 was popular a decade ago) and authorities now don't consider that to provide adequate margin so standards and good practices now require 2048 and occasionally more. – dave_thompson_085 May 27 '22 at 20:38
  • C doesn't include support for big integers. Either you use a library or you program everything yourself. In the latter case, please don't come here to ask for support, as there is little to no difference from copying the code from an open source library anyway. – Maarten Bodewes May 27 '22 at 22:32
  • The standard library for arbitrary-precision arithmetic in C is [GMP](https://gmplib.org/). It's pretty easy to use. (Oh, but, wait, you said you don't want to use any libraries.) – Steve Summit May 27 '22 at 22:34
  • @MaartenBodewes Why shouldn't people ask here about problems they might have implementing their own bignum code? I'd say it's an excellent learning exercise — far better than most of the insipid problems we get people asking about every day. – Steve Summit May 27 '22 at 22:36
  • @user1231247 If you want to implement your own computation functions for "big" numbers, you certainly can. It's an instructive and rewarding exercise, but not one you're going to finish in an hour, or even an afternoon. First you have to pick your representation. Popular choices are (1) an array of decimal digits and (2) an array of unsigned int. For (1) you'll do arithmetic in base 10, for (2) you'll do it in base 32768 or base 65536 or base 2147483648 or base 4294967296, which is considerably more efficient, but a bit harder to think about at first. – Steve Summit May 27 '22 at 22:42
  • 1
    You can do just about all your basic calculations using easy variations on the techniques you learned for doing digit-at-a-time arithmetic in elementary school. (Division is harder, though.) – Steve Summit May 27 '22 at 22:43
  • You can get some ideas from the answers at [this question](https://stackoverflow.com/questions/72013383), and [this one](https://stackoverflow.com/questions/66109785). – Steve Summit May 27 '22 at 22:45
  • 1
    @SteveSummit Sure you can ask *specific* questions. But we assume that you perform some kind of research, try things out yourself, instead of dumping a conversion problem on our lap. I mean, converting your code would depend on the bignum functions used, right? And you want us to code those too for you? I mean, it's not like [it's X-mas](https://stackoverflow.com/a/14027143/589259). – Maarten Bodewes May 27 '22 at 22:45

0 Answers0