This paper proposes a data encryption method based on a modified McEliece cryptosystem, in which classic Goppa codes are replaced by error-correcting codes from the Redundant Residue Number System (RRNS). The construction of the RRNS code’s generator matrix and the formation of the public key as a composition of the G matrix, a scrambling matrix S, and a permutation matrix P have been described. An approach has been developed for selecting the RRNS moduli system, ensuring the necessary code parameters and the highest possible rank of the generator matrix. A study of the statistical and structural properties of the public key (entropy of elements, value distribution, density, rank), as well as their impact on the cryptosystem’s resistance to ISD-type attacks, has been conducted. A software implementation of key generation and the encryption/decryption processes has been presented, along with experimental results from attack simulations for various RRNS code parameters. Based on the analysis, recommendations have been formulated regarding the choice of moduli, the structure of scrambling matrices, and code parameters to achieve a post-quantum security level with an acceptable public key size.
[1] Agrawal, R., Bu, L., & Kinsy, M. A. (2020, October). Quantum-proof lightweight McEliece cryptosystem co- processor design. In 2020 IEEE 38th International Conference on Computer Design (ICCD) (pp. 73-79). IEEE. DOI: https://doi.org/10.1109/ICCD50377.2020.00029
[2] Chen, M. S., & Chou, T. (2021). Classic McEliece on the ARM cortex-M4. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021 (3), 125-148. DOI: https://doi.org/10.46586/tches.v2021.i3.125-148.
[3] Chen, P. J., Chou, T., Deshpande, S., Lahr, N., Niederhagen, R., Szefer, J., & Wang, W. (2022). Complete and improved FPGA implementation of classic McEliece. IACR Trans- actions on Cryptographic Hardware and Embedded Systems, 2022 (3), 71-113. DOI: https://doi.org/10.46586/ tches.v2022.i3.71-113
[4] Chou, T. (2018). McBits revisited: Toward a fast constant-time code-based KEM. Journal of Crypto- graphic Engineering, 8, 95–107. DOI: https://doi.org/ 10.1007/s13389-018-0186-9
[5] Iqbal, S. S., & Zafar, A. (2025). Optimizing code-based cryptography for efficient and secure post-quantum key agreement. Procedia Computer Science, 259, 1034-1048.DOI: https://doi.org/10.1016/j.procs.2025.04.057
[6] Kostalabros, I. V., Ribes, J., Carril, X., Farras, O., Hernandez, C., & Moreto, M. (2025). Leveraging HLS to design a versatile & high-performance classic McEliece accelerator. ACM Transactions on Embedded Computing Systems, 24 (5), 1-27. DOI: https://doi.org/ 10.1145/3698395
[7] Li, Z., Xing, C., & Yeo, S. L. (2019). Reducing the key size of McEliece cryptosystem from automorphism- induced Goppa codes via permutations. In D. Lin & K. Sako (Eds.), Public-Key Cryptography – PKC 2019: Lecture Notes in Computer Science (Vol. 11443). Springer, Cham. DOI: https://doi.org/10.1007/978-3-030- 17259-6_20
[8] López-García, M., & Cantó-Navarro, E. (2020, February). Hardware-software implementation of a McEliece cryptosystem for post-quantum cryptography. In Future of Information and Communication Conference (pp. 814-825). Springer. DOI: https://doi.org/10.1007/ 978-3-030-39442-4_60
[9] Moody, D., Perlner, R., Regenscheid, A., Robinson, A., & Cooper, D. (2024). Transition to post-quantum cryptography standards (NIST Internal Report 8547 ipd). National Institute of Standards and Technology.DOI: https://doi.org/10.6028/NIST.IR.8547.ipd
[10] Singh, H. (2019). Code based cryptography: Classic McEliece (arXiv:1907.12754). arXiv.DOI: https://doi.org/10.48550/arXiv.1907.12754
[11] Xiao, H., Garg, H. K., Hu, J., & Xiao, G. (2016). New error control algorithms for residue number system codes. Etri Journal, 38 (2), 326-336.DOI: https://doi.org/10.4218/etrij.16.0115.0575
[12] Yatskiv, V., Kulyna, S., Yatskiv, N., & Kulyna, H. (2020). Protected distributed data storage based on residue number system and cloud services. 2020 10th International Conference on Advanced Computer Information Technologies (ACIT) (pp. 796-799).DOI:10.1109/ACIT49673.2020.9208849
[13] Yatskiv, V., Yatskiv, N., Ivasiev, S., Kulyna, S., Tsavolyk, T., & Yatskiv, I. (2025). The McEliece cryptosystem based on the redundant residue number system. 2025 15th International Conference on Advanced Computer Information Technologies (ACIT) (pp. 573- 577). IEEE. DOI:10.1109/ACIT65614.2025.11185887
[14] Zhu, Y., Zhu, W., Chen, C., Zhu, M., Li, Z., Wei, S., & Liu, L. (2023, July). McKeycutter: A high-throughput key generator of classic McEliece on hardware. In 2023 60th ACM/IEEE Design Automation Conference (DAC) (pp. 1-6). IEEE. DOI: https://doi.org/10.1109/ DAC56929.2023.10247918