C语言 费奇菲亚特沙米尔计划不起作用

Question

我正在尝试在 C （Arduino） 中实现 Feige Fiat Shamir 识别方案并且它可以工作，但仅在e = 0时。当e = 1它不起作用时。

我怎样才能让它工作？

#include <Wire.h>
int getGCD(int a, int b)
{
   int c;
   while (a != 0)
   {
      c = a;
      a = b % a;
      b = c;
   }
   return b;
}
int getCoprime(int n)
{
   int coprime;
   do
   {
      coprime = random(1, n);
   } 
   while (getGCD(n, coprime) != 1);
   return coprime;
}

//Preparation
int n = 7 * 3;
int s = getCoprime(n);
int v = (s * s) % n;
void loop ()
{
  e = random(0, 2);
  r = random(1, n);
  int y = (r * (int)pow(s, e)) % n;
  int x = (r * r) % n;
  int ysqmodn = y * y % n;
  int test = (x * (int)pow(v, e)) % n;
  if(ysqmodn == test)
  {
    Serial.print("The current ICC matches. n");
  }  
  else
  {  
    Serial.print(String(e));
    Serial.print("n");
  }
  delay(500);
}

Answer 1

它在e==1时确实有效。当e==0时，计算是微不足道的，因为 s 和 v 由于 0 的幂总是 1 而消失。这是复制和更改的代码，仅足以使其编译。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
int random (int low, int high) {
    return low + rand() % (high - low);
}
int getGCD(int a, int b) {
    int c;
    while (a != 0)
    {
        c = a;
        a = b % a;
        b = c;
    }
    return b;
}
int getCoprime(int n) {
    int coprime;
    do
    {
        coprime = random(1, n);
    } 
    while (getGCD(n, coprime) != 1);
    return coprime;
}
int main(void) {
        int e, x, y, r, n, s, v, test, ysqmodn;
        srand((unsigned)time(NULL));
        n = 7 * 3;
        s = getCoprime(n);
        v = (s * s) % n;
        e = random(0, 2);
        r = random(1, n);
        printf("n=%d, s=%d, e=%d, r=%dn", n,s,e,r);
        y = (r * (int)pow(s, e)) % n;
        x = (r * r) % n;
        ysqmodn = y * y % n;
        test = (x * (int)pow(v, e)) % n;
        if(ysqmodn == test)
            printf("The current ICC matches. n");
        else
            printf("%dn", e);
        return 0;
    }

示例结果：

n=21, s=2, e=1, r=2
The current ICC matches.
n=21, s=11, e=0, r=12
The current ICC matches.
n=21, s=8, e=1, r=14
The current ICC matches.
n=21, s=17, e=1, r=13
The current ICC matches.
n=21, s=1, e=0, r=9
The current ICC matches.
n=21, s=4, e=0, r=13
The current ICC matches.