1

I am new to programming and I have a coding homework. We have to implement RSA using MPIR. I generated p and q the best way I could think of. I could not make them 512 bits, but I will continue as it is. I also did not test for primality yet. I will deal with the byte size and primality test if I have time.

My problem is regarding finding Phi(n) = (p-1)*(q-1). I manage to find p, q and N, but Phi(n) and N give the same result. I checked the functions in the MPIR document multiple times and I tried two similar functions for substraction as you will see, but still no luck. (I did not write the code for q here as it is a repetition of p.)

Can someone guide me? I would like to say thank you in advance.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <mpir.h>
#include <cstdlib> 
#include <iostream>

using std::cout;
using std::cin;


   int main()
   {

    mpz_t p;
    mpz_init(p); 

    mpz_t randint;
    mpz_init(randint);

    gmp_randstate_t state;
    gmp_randinit_mt(state);

    mpir_ui seed;


    cout << "Please choose a number for the seed of the random number 
    generator:";
    cin >> seed;

    gmp_randseed_ui(state, seed);
    mpz_urandomb(randint, state, 512); 

    mpz_t limit;
    mpz_init(limit);
    mpz_t winner;
    mpz_init(winner);


    mpz_ui_pow_ui(limit, 2, 511);

    mpz_ior(winner, limit, randint);

    mpz_next_prime_candidate(p, winner, state);

    gmp_randclear(state);
    mpz_clear(randint);
    mpz_clear(winner);

    mpz_t q;
    mpz_init(q);

    mpz_init(randint);
    gmp_randinit_mt(state);

    cout << "Please choose a number for the seed for the random number 
    generator :";
    cin >> seed;


    gmp_randseed_ui(state, seed);
    mpz_urandomb(randint, state, 512);


    mpz_init(limit);

    mpz_init(winner);

    mpz_ui_pow_ui(limit, 2, 511);

    mpz_ior(winner, limit, randint);

    mpz_next_prime_candidate(q, winner, state);

    gmp_randclear(state);
    mpz_clear(randint); 
    mpz_clear(limit);
    mpz_clear(winner);


   // Now we find n=p*q
 
    mpz_t N; 
    mpz_init(N);

    mpz_mul(N, p, q);


    mpz_t phin;
    mpz_init(phin);


    mpz_t pa;
    mpz_init(pa);
    mpz_t qa;
    mpz_init(qa);

1st way

    mpz_t one;
    mpz_init(one);
    mpz_set_ui(one, 1);


    mpz_sub(pa, p, one); 
    mpz_sub(qa, q, one);

    mpz_mul(phin, pa, qa);

Second way

    mpz_sub_ui(pa, p, 1); 
    mpz_sub_ui(qa, q, 1);

    mpz_mul(phin, pa, qa);

Then I write them to a document and clear everything.

Cero
  • 11
  • 3
  • You find a prime `p` but where did you find prime `q`. The first rule of coding is good testing and that starts with printing values. – kelalaka Apr 30 '21 at 18:29
  • A used the same functions to find q and I found a different number. I thought it would make the code too long to write q, but I will edit the question and include it. – Cero Apr 30 '21 at 19:15
  • https://gist.github.com/akosma/865b887f993de462369a04f4e81596b8 – kelalaka Apr 30 '21 at 19:24
  • @kelalaka They used the same functions for Phi as I did, so I don't know where I did wrong. However, I did not know about assert, it will make things much easier. Thank you. – Cero Apr 30 '21 at 19:34
  • Note that the site I linked uses the [Carmichael function](https://crypto.stackexchange.com/a/88368/18298) that gives the smallest RSA exponent. Since you did not post [Minimal, Verifiable Code](https://stackoverflow.com/help/minimal-reproducible-example) one cannot look your mistake easily. – kelalaka Apr 30 '21 at 19:48
  • @kelalaka Hmm, I did not notice that, thanks for pointing it out. We were thought that we use multiplication, so LCM didn't even occur to me. – Cero Apr 30 '21 at 20:02
  • Well, not everybody teaches in this way. Original RSA was using the Eular's Phi as you did. Later, Carmichael function become the standard since it can reduce the private key operations by providing the minimal working exponent. Therefore, don't surprise if you see [more than one working private exponent](https://crypto.stackexchange.com/q/87583/18298) – kelalaka Apr 30 '21 at 20:07
  • 1
    @kelalaka I just saw a post about that! That explains it. Thanks again. – Cero Apr 30 '21 at 20:15
  • Welcome, and have fun in coding. – kelalaka Apr 30 '21 at 20:17

0 Answers0