python - 计算大十六进制数的模而不溢出

Question

我正在尝试做一些签名的密码学问题，但我的值是十六进制的，并且它们太高而无法在 SageMaths 上计算而不会在 python 和 sage 中溢出。我该如何解决这个问题？我尝试的贤者代码如下。

在 python 和 sage 中尝试

N = ZZ(0xe55c85be1e8f31b8cfa79da46e313545fe58d51308f427be1798373cce2304c0cee692f4ab78387dc5d3161b5a1f33df90858c5c0a8fe906579257043a527f33e37b3466b7929be81abec6e9979215abf92d71032caf5fffe4a5f1c176172d8fb62da7beecc255e45b75a44e30ebbeb91ecb97de7dc51a0c1d19f1cb0e5658b4a66cd4500252dc8f50076c357f5dece3f94ef1133cd2c592a5c9eb22a2e818f95252f0917caf47737807ece3a0f508f1af03b8eabd2f3d6cc881b27627e3cb5eda7862c25213592ebf1f8470dff22d7603d299ee69628101c75133d65618692aad5f3b2ffb3a22e1084a900cb0543107b02f8062737181eab4870cf25f0ed473cf4095530702314dd0a8cace3a6fd0169f2dfea254d3ab152381c3ae535f780a1b532fe040eae7ba864bf28543a6dec711e62878ec4471341c8ee00824e9cae7627c29de36f3678cbfe046dce37bd6c7639c51f9387e1b756bda7622efb9ee49fb258266b19fb359ef3f959ffabb0ebf3747bb923cf69899bfdcaba18bd4dbb7, 16)

D = ZZ(0x541af9701e04a45700ce962015c835a0d503fe1e5cca2b48a99e47a32473f2ea40f48c2eec31c98555657255d5565bcf3f4fb98886d6febc34a0950817dae88a3e808f569b3a47b1751d4013a861095166ae2322e6dfe8740d844c8284ab3b29d7c4261efcf2c64c56bd6ce2bf4db3426ee879683cf669f6c7351c55398cb03a8e4c9a0e3ccbe5d527a3912a8cea045414b7bdef2ffe9a348c56dec274ba676e05a224553543910fe6940169f73be36bbca1c0cd53525f53e4b2aa9e69423ef077b2d1bfe8d45927a677f74418240b95ed5c698e62fb429ece5fabbdcff8f64c480bff46bb6a448ae350739795abd156a5814378248b7100bfbaa07b039bc105a32a6fe74e07688577edecd515bd452a41cbfc017b9d26e76a5bec2ce433714a02f0f2c3784b65738adc849c3c31f8a731132e4bd8c2b2c0b33de87403c2b7ff12ab3d9582453844b4ff03142f899b256e407c3301adc46794d14bd668beac877e9cb5aa0602c447b75d3424d3a71495ed55a86fb1b01b5fbae2a766f6172301, 16)

M = ZZ(0x6b948843b86adb04a834cba6a76d5753da8ffbdcd01782a49d395f52f4c37a0cc39eeb41646ebc2b2003bacb203328e210604f248e02fa95aa6eec50751abe267f5c0b70f60901a4fd338f61bb2000acb3f2cf80d602acf85c5ee2f015667e9520e2d5c1aa84dcc69c9358a376846d2a0e9b52877fe17a76ce4bf6c46c7a46f61102d42869e0a594c4ad71a699a603654e4d6bdf83fc09b9741b70e82013302517efceebc9be49a7bc86ab89653f3281ffcc20824970410461510f4a9b538f8d5468b872cbef23a348b61576ae1f840138f14e7f8f13643aae1467cd534803555f8b2facb34fae15d53dc8c954bc8af0561597bfbb5a82c3b08bc83d349962aaaa6e164a138045b96dd9730aa7e1bb440838c42296ff2bdf53ca69f09c7e74c5e855455ffb052399e82e7e182d8efa08c96bdd166a00381d3fc53bb2a3d46b0aa6e2af8a45cd00e8bffe34fb7bafd20dade1efece7331b417136e2ed971c8f16e193948f3c6595e9f63a948610f1d3e2246e6603d0b039f9bdd50fc50baadef, 16)

Z = M^D

SIG = mod(Z, N)

print(SIG)

<小时/>

OverflowError: exponent must be at most 9223372036854775807

Answer 1

Python 中的 pow 函数假装计算它:

>>> hex(pow(M, D, N))
'0x274e84c26582b994d2fda202d6774579e9124d4f07e0620c35df8f499fdf9ed1736703d0d613bb805ec1030f6a9130fbdcf5a0f2dacf23bd9382b8112309b0fbccae7115d4a68d4660f2b86758b8b16a0affa96ac9776934d4cf55d9ad64bf3a4b3adee1cc0633401319ac77d76cf6b79835b1c831a787b4e1f78d615b6a50856f15d08dcd94215a99644b822437ba1bb27dc4ef5e3d30e661bed7c598159854683ded1da06939ece2239daf6d3207d8f093a10210c12e3c405f3f7d4d89e2fca7c9d8b2272ddd6eaba0ff8f553f9e0a3440e82db55bc053727474f0701e45da59a5ef02f5307e9ae8ade39862e8ccdcc14d3107485bcf5c7bb01600ff8932f126561a474c41fc23d9af4651f2c8415d19a2514c37f37b360243149573afabdcc4aa1db33f9346e89006d5577dcbb1ddd31db28b89f48c4f8f4bb0c61bb66b9c2998a1b7229f372e1e2e3d14905f1c6f9e37dd0acbabe1fad962fd2d12d162a8aeb9879702984ecdbf4978a5bfdf2b6204eeb077f0dab98d1e815edd26a66f49'