filter-bad.c

// copri, Attacking RSA by factoring coprimes
//
// License: GNU Lesser General Public License (LGPL), version 3 or later
// See the lgpl.txt file in the root directory or <https://www.gnu.org/licenses/lgpl>.

// This file contains a balanced split util application
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <gmp.h>
#include "copri.h"

#define PRODUCT_1000PRIMES "678629608419755514953266004896957820972161078160377361970324401521111792080121479864721936071815069425907219215791646774510151130705671056416094404541167439287735488353736963531288441938981088407654256240451529081607242659988552012480001287133802278572298314458227654950008738955663072953766341488209509227159933381319371567666804963833249523370831655778314080604712246344649628072459805028063160913071005795183295590443375991860551286230065601580359306757988823124262933259305966372664091680948986620887898883461227980556352852601733860114246410887151983493540958775872577571329277597701163671587052591794386970584444752423596023268793021595936555282977008138833858707329536639661377014042325817639809356799596347944462538427778375525904007169834445567450156949173690701738594584875536885957881452438269676946038980597530032671949818526703398270502591574889228837327819994695664173214894557366363343168494592437205324652573516528943874382178600874878024643322031797588414862315122048846223291257900756812820806739795819803783834366449110996030165071920678407750230118672657378102915524688059208755108467225277065866103666795739208709483959119145497860116133180335757702319385020561042517429031288526721801002679092058170909635701703382390753126302005323612316630558515594616479515096004453718500060291836932140612551722161051067379805065002788004096547708243964735215852734827632098700684466036892770059458754742495711074949314613079781545359495019757827538184361308856825999513366660884541936335491466045305322353749545362962683762333460252556042583248154845846566948014188971651057314058851019340282646752239847232045463969939303431371658607220786663205842510175297602195433569758123945251755043878718459161595137019904240640962465899496512410906852088532419874383895656303779315512987369934711061777117329635461569528504994783413643047392160871963795694958724055597996525917454740621526108635321204763824742430011606570436994644169759611263012712375861911682673548369764923418748711813157811279361700331599397588282864147719911156923709896847720603482450047076226728760035577410722701184878333100234780537897462936378382079055966277885316116887834607362114802378706815302650083359076798475953780285866955566883261644281750278358349579977889429105626865087038835977930842352223971442123281019745568694318200865586150762549114357677130353514342849892002965601064686292493671204318349298134598116662388818407027989992498970986262856712232401426575229549744739851333516937170071337085705197690437625282926914858257689908846227286051735284322402597283976180484905838486513162987381659809287870592690902387482033879184700359561190209417618607868793293476867624464497838299321267571049753373623085351455438610076341961842557148160442782839736179329056237366708383637405663196770746783100179128651460773512143616414356080816160456447832856222804164147618891013658880373227849181446498052320436905124576367614898030410445386643656246089772967461562154147355201124738052009172637452710027640262529821855681129322547617443299372089380860873141895162966481252930360380537684913059090577224188204179681342669502124011214018434733385892140553307905100266308832521127607403573729242486985024795253305646999864066282626291530104297235324933472771821035277094700384260778312268190937365143307612108901729316774669077441981239149913617114331308200242717771235228048768133852203532299832810943137983635951570"

// The generic `main` function.
//
// Define all variables at the beginning to make the C99 compiler
// happy.
int main(int argc, char **argv) {
  mpz_array s, good, bad;
  size_t count, i, wc;
  int c, vflg = 0, jflg = 0, hflg = 0, errflg = 0;
  char *filename = "primes.lst";
  char *out_good_filename = NULL;
  char *out_bad_filename = NULL;
  mpz_t product, gcd;
  double percentage;

  mpf_set_default_prec(64);

  // #### argument parsing
  // Boring `getopt` argument parsing.
  while ((c = getopt(argc, argv, ":vhjb:g:")) != -1) {
    switch(c) {
    case 'b':
      out_bad_filename = optarg;
      break;
    case 'g':
      out_good_filename = optarg;
      break;
    case 'v':
      vflg++;
      break;
    case 'h':
      hflg++;
      break;
    case 'j':
      jflg++;
      break;
    case ':':
      fprintf(stderr, "Option -%c requires an operand\n", optopt);
      errflg++;
      break;
    case '?':
      fprintf(stderr, "Unrecognized option: '-%c'\n", optopt);
      errflg++;
    }
  }

  if (optind == argc - 1) {
    filename = argv[optind];
  } else {
    errflg++;
  }

  // Print the usage and exit if an error occurred during argument parsing.
  if (errflg || hflg > 0) {
    fprintf(stderr, "usage: [-v] [-o FILE] [file]\n"\
                    "\n\t-b FILE   to store the bad keys"\
                    "\n\t-g FILE   to store the bod keys"\
                    "\n\t-j        print json messages"\
                    "\n\t-v        be more verbose"\
                    "\n\n");
    exit(2);
  }

  // Load the integers.
  array_init(&s, 10);
  count = array_of_file(&s, filename);
  if (count == 0) {
    fprintf(stderr, "Can't load %s\n", filename);
    return 1;
  }
  if (s.used != count) {
    fprintf(stderr, "Array size and load count do not match\n");
    return 2;
  }
  if (s.used == 0) {
    fprintf(stderr, "No integers loaded (empty file)\n");
    return 3;
  }

  if (out_bad_filename != NULL && vflg > 0) {
    printf("bad keys are going to be saved in '%s'\n", out_bad_filename);
  }

  if (out_good_filename != NULL && vflg > 0) {
    printf("good keys are going to be saved in '%s'\n", out_good_filename);
  }

  mpz_init(product);
  mpz_set_str(product, PRODUCT_1000PRIMES, 10);

  if (vflg) {
    printf("filter %zu integers\n", s.used);
  }

  mpz_init(gcd);
  array_init(&good, 10);
  array_init(&bad, 10);
  for(i=0; i<s.used; i++) {
    if (vflg && i % 10000 == 0) {
      percentage = ((double) i) / ((double) s.used) * 100.0;
      printf("%.2f%% (%zu of %zu)\n", percentage, i, s.used);
    }
    mpz_gcd(gcd, s.array[i], product);
    if (mpz_cmp_ui(gcd, 1) != 0) {
      array_add(&bad, s.array[i]);
    } else {
      array_add(&good, s.array[i]);
    }
  }

  if (vflg) {
    printf("found %zu bad and %zu good integers\n", bad.used, good.used);
  }

  if (out_good_filename != NULL) {
    wc = array_to_file(&good, out_good_filename);
    if (good.used != wc) {
      fprintf(stderr, "Array size and write count do not match\n");
      return 4;
    }
  }

  if (out_bad_filename != NULL) {
    wc = array_to_file(&bad, out_bad_filename);
    if (bad.used != wc) {
      fprintf(stderr, "Array size and write count do not match\n");
      return 4;
    }
  }

  array_clear(&bad);
  array_clear(&good);
  array_clear(&s);
  mpz_clear(product);
  mpz_clear(gcd);
}