Helpex - Trao đổi & giúp đỡ Đăng nhập
24

Tôi đang sử dụng Thuật toán RSA để mã hóa / giải mã và để giải mã các tệp, bạn phải xử lý một số giá trị khá lớn. Cụ thể hơn, những thứ như

P = C^d % n
  = 62^65 % 133

Bây giờ đó thực sự là những tính toán duy nhất mà tôi đang làm. Tôi đã thử sử dụng Thư viện BigInteger của Matt McCutchen, nhưng tôi gặp rất nhiều lỗi trình biên dịch trong quá trình liên kết, chẳng hạn như:

encryption.o(.text+0x187):encryption.cpp: undefined reference to `BigInteger::BigInteger(int)'

encryption.o(.text+0x302):encryption.cpp: undefined reference to `operator<<(std::ostream&, BigInteger const&)'

encryption.o(.text$_ZNK10BigIntegermlERKS_[BigInteger::operator*(BigInteger const&) const]+0x63):encryption.cpp: undefined reference to `BigInteger::multiply(BigInteger const&, BigInteger const&)'

Vì vậy, tôi đã tự hỏi đâu sẽ là cách tốt nhất để xử lý các số nguyên thực sự lớn từ Thuật toán RSA.

Tôi nghe nói rằng một khả năng sẽ là khai báo các biến của bạn dưới dạng dài gấp đôi, vì vậy ...

long long decryptedCharacter;

nhưng tôi không chắc chắn chính xác độ lớn của một số nguyên có thể lưu trữ.


Ví dụ: tôi cố gắng biên dịch và chạy chương trình sau bằng cách sử dụng dev C ++:

#include iostream

#include "bigint\BigIntegerLibrary.hh"

using namespace std;

int main()
{
    BigInteger a = 65536;
    cout << (a * a * a * a * a * a * a * a);
    return 0;
}

thì tôi nhận được những lỗi đó.

Derek, tôi nghĩ rằng bằng cách bao gồm BigIntegerLibrary.hhtệp, trình biên dịch sẽ duyệt qua và biên dịch tất cả các tệp cần thiết mà nó sẽ sử dụng.

Tôi nên thử và biên dịch chương trình ở trên như thế nào để giải quyết các lỗi liên kết?

24 hữu ích 4 bình luận 79k xem chia sẻ
15 trả lời 15
13

Tomek, có vẻ như bạn không liên kết đúng với mã BigInteger. Tôi nghĩ bạn nên giải quyết vấn đề này hơn là tìm kiếm một thư viện mới. Tôi đã xem qua nguồn và BigInteger::BigInteger(int)được xác định chắc chắn nhất. Một cái nhìn ngắn gọn cho thấy rằng những người khác cũng vậy.

Các lỗi liên kết mà bạn gặp phải ngụ ý rằng bạn đang bỏ qua việc biên dịch nguồn BigInteger hoặc bỏ qua việc bao gồm các tệp đối tượng kết quả khi bạn liên kết. Xin lưu ý rằng nguồn BigInteger sử dụng phần mở rộng "cc" thay vì "cpp", vì vậy hãy đảm bảo rằng bạn cũng đang biên dịch các tệp này.

13 hữu ích 0 bình luận chia sẻ
12

Tôi khuyên bạn nên sử dụng gmp , nó có thể xử lý các int dài tùy ý và có các ràng buộc C ++ phù hợp.

afaik trên phần cứng / phần mềm dài hiện tại là 64bit, do đó, unsigned có thể xử lý các số lên đến (2 ** 64) -1 == 18446744073709551615, nhỏ hơn một chút so với các số bạn phải xử lý với RSA.

12 hữu ích 1 bình luận chia sẻ
3

Để xem kích thước của một đoạn dài, hãy thử điều này:

#include <stdio.h>

int main(void) {
    printf("%d\n", sizeof(long long));

    return 0;
}

Trên máy tính của tôi, nó trả về 8 có nghĩa là 8 byte có thể lưu trữ 2 ^ 64 giá trị.

3 hữu ích 0 bình luận chia sẻ
3

Đối với RSA, bạn cần một thư viện bignum. Các con số quá lớn để phù hợp với độ dài 64 bit. Tôi từng có một đồng nghiệp ở trường đại học được giao nhiệm vụ triển khai RSA bao gồm cả việc xây dựng thư viện bignum của riêng anh ấy.

Khi nó xảy ra, Python có một thư viện bignum. Việc viết các trình xử lý bignum đủ nhỏ để phù hợp với một bài tập về khoa học máy tính, nhưng vẫn có đủ kỹ năng để biến nó thành một nhiệm vụ không hề nhỏ. Giải pháp của anh ấy là sử dụng thư viện Python để tạo dữ liệu thử nghiệm nhằm xác thực thư viện bignum của anh ấy.

Bạn sẽ có thể tải các thư viện bignum khác.

Ngoài ra, hãy thử triển khai một nguyên mẫu bằng Python và xem nó có đủ nhanh hay không.

3 hữu ích 0 bình luận chia sẻ
3

Nếu bạn không triển khai RSA dưới dạng bài tập ở trường hoặc thứ gì đó, thì tôi khuyên bạn nên xem thư viện crypto ++ http://www.cryptopp.com

Thật dễ dàng để triển khai các công cụ tiền điện tử một cách tệ hại.

3 hữu ích 0 bình luận chia sẻ
3

Đây là cách tiếp cận của tôi, nó kết hợp phép tính lũy thừa nhanh bằng cách sử dụng phép lũy thừa bình phương + mô-đun giúp giảm không gian cần thiết.

long long mod_exp (long long n, long long e, long long mod)
{
  if(e == 1)
  {
       return (n % mod);
  }
  else
  {
      if((e % 2) == 1)
      {
          long long temp = mod_exp(n, (e-1)/2, mod);
          return ((n * temp * temp) % mod);
      }
      else
      {
          long long temp = mod_exp(n, e/2, mod);
          return ((temp*temp) % mod); 
      }
  }
}
3 hữu ích 0 bình luận chia sẻ
3

Có nhiều thứ để đảm bảo việc triển khai RSA hơn là chỉ những con số lớn. Việc triển khai RSA đơn giản có xu hướng làm rò rỉ thông tin cá nhân qua các kênh phụ, đặc biệt là thời gian (nói một cách đơn giản: thời gian tính toán phụ thuộc vào dữ liệu được xử lý, điều này cho phép kẻ tấn công khôi phục một số, có thể là tất cả, các bit khóa cá nhân). Việc triển khai RSA tốt thực hiện các biện pháp đối phó.

Ngoài ra, ngoài phép tính lũy thừa mô-đun, có toàn bộ hoạt động kinh doanh đệm, không khó về mặt khái niệm, nhưng, vì tất cả mã I / O và phân tích cú pháp, đều có chỗ cho các lỗi nhỏ. Mã dễ viết nhất là mã đã được viết bởi người khác.

Một điểm khác là khi bạn đã thiết lập và chạy mã RSA của mình, bạn có thể bắt đầu hình dung ra các tiện ích mở rộng và các tình huống khác, ví dụ: "điều gì sẽ xảy ra nếu khóa riêng tư tôi muốn sử dụng không nằm trong RAM mà nằm trong thẻ thông minh?". Một số triển khai RSA hiện có thực sự là API có thể xử lý điều đó. Trong thế giới Microsoft, bạn muốn tra cứu CryptoAPI , được tích hợp trong Windows. Bạn cũng có thể muốn xem NSS , là thứ mà trình duyệt Firefox sử dụng cho SSL.

Tóm lại: bạn có thể xây dựng triển khai tuân thủ RSA từ các số nguyên lớn, nhưng điều này khó thực hiện chính xác hơn những gì thường thấy, vì vậy lời khuyên của tôi là sử dụng triển khai RSA hiện có.

3 hữu ích 0 bình luận chia sẻ
2

Tôi sẽ dùng thử thư viện GMP - nó mạnh mẽ, được thử nghiệm tốt và thường được sử dụng cho loại mã này.

2 hữu ích 0 bình luận chia sẻ
2

Openssl cũng có một loại Bignum mà bạn có thể sử dụng. Tôi đã sử dụng nó và nó hoạt động tốt. Dễ dàng gói trong một ngôn ngữ oo như C ++ hoặc mục tiêu-C, nếu bạn muốn.

https://www.openssl.org/docs/crypto/bn.html

Ngoài ra, trong trường hợp bạn không biết, để tìm câu trả lời cho phương trình dạng x ^ y% z này, hãy tìm một thuật toán gọi là lũy thừa mô-đun. Hầu hết các thư viện tiền điện tử hoặc bignum sẽ có một chức năng dành riêng cho việc tính toán này.

2 hữu ích 0 bình luận chia sẻ
1

Một int dài thường là 64 bit có thể không đủ để xử lý một số nguyên lớn như vậy. Có thể bạn sẽ cần một thư viện bigint nào đó.

Xem thêm câu hỏi này trên Stack Overflow

1 hữu ích 0 bình luận chia sẻ
1

Kiểm tra tài liệu trình biên dịch của bạn. Một số trình biên dịch có các kiểu được định nghĩa như __int64 cung cấp cho bạn kích thước của chúng. Có thể bạn đã có sẵn một số trong số chúng.

1 hữu ích 0 bình luận chia sẻ
1

Chỉ cần lưu ý: __int64 và long dài là phần mở rộng không chuẩn. Không ai được đảm bảo sẽ được hỗ trợ bởi tất cả các trình biên dịch C ++. C ++ dựa trên C89 (nó ra đời vào năm 98, vì vậy nó không thể dựa trên C99)

(C đã hỗ trợ 'lâu dài' kể từ C99)

Nhân tiện, tôi không nghĩ rằng số nguyên 64bit giải quyết được vấn đề này.

1 hữu ích 2 bình luận chia sẻ
1

Tôi đã gặt hái được nhiều thành công khi sử dụng thư viện LibTomCrypt cho nhu cầu tiền điện tử của mình. Nó nhanh chóng, gọn gàng và di động. Nó có thể thực hiện RSA của bạn cho bạn hoặc chỉ xử lý phép toán nếu bạn muốn.

1 hữu ích 0 bình luận chia sẻ
0

Thực tế là bạn gặp sự cố khi sử dụng thư viện biginteger nào đó không có nghĩa là đó là một cách tiếp cận tồi.

Sử dụng lâu dài chắc chắn là một cách tiếp cận tồi.

Như những người khác đã nói đã sử dụng thư viện biginteger có lẽ là một cách tiếp cận tốt, nhưng Bạn phải đăng thêm thông tin chi tiết về cách bạn sử dụng thư viện đã đề cập để chúng tôi có thể giúp Bạn giải quyết những lỗi đó.

0 hữu ích 0 bình luận chia sẻ
0

Tôi đã sử dụng GMP khi viết triển khai RSA.

0 hữu ích 0 bình luận chia sẻ
loading
Không tìm thấy câu trả lời bạn tìm kiếm? Duyệt qua các câu hỏi được gắn thẻ c++ rsa biginteger integer , hoặc hỏi câu hỏi của bạn.

Có thể bạn quan tâm

loading