{"entities":{"Q4364558":{"pageid":6394157,"ns":120,"title":"Item:Q4364558","lastrevid":108298526,"modified":"2026-11-05T19:55:45Z","type":"item","id":"Q4364558","labels":{"en":{"language":"en","value":"`Pseudo-random' number generation within cryptographic algorithms: The DDS case"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1088241"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4364558$E851A26E-BB56-483C-977A-79D6663E7922","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b33a496c39b5a319ce4def2441635e2be3200c55","datavalue":{"value":"0893.94044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4364558$7A601327-B4B2-4986-BA94-201958141639","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1f100798c61b0ceeb4781412ea9101bded8b187","datavalue":{"value":{"entity-type":"item","numeric-id":171914,"id":"Q171914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4364558$C732EB66-2103-4263-8A90-748EB21DB782","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1e09504f5af03937ba3bdae7ee664e73c54fb3be","datavalue":{"value":{"entity-type":"item","numeric-id":814417,"id":"Q814417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4364558$371ABF8C-DA20-4ED8-AE27-D59845A735A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"46a19aabcc7af8f26d97e8183ee72dbc292f645f","datavalue":{"value":{"entity-type":"item","numeric-id":6480587,"id":"Q6480587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4364558$32488162-F2C3-4124-9892-51C39B20CF6C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b0eaf19f8434564cff6a93a80be5427b161bea94","datavalue":{"value":{"time":"+1998-01-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4364558$8E33EE77-4E85-4B39-BDCE-CC3459E9AEFA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4364558$BAB1ED8B-F11F-4D99-A89F-A9E90FFE0167","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c6dc32161cfbbc0543faafed5e6c564351d5db2f","datavalue":{"value":"65C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4364558$FF94023D-E8A0-4D99-9264-0C760426A927","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"72df94cdde3cc56281a8e3081d079598762befa1","datavalue":{"value":"1088241","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4364558$D2450E47-A89D-46AF-909C-7CCF5F353367","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"323a6879b642061d961b1cf6e1749f69c1b7f502","datavalue":{"value":"Digital Signature Standard","type":"string"},"datatype":"string"},"type":"statement","id":"Q4364558$E3BC225C-E903-41BB-8015-673EF5D1348C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b5b2e507b1506c0a809acb78ce7384d267aebc6","datavalue":{"value":"secret key","type":"string"},"datatype":"string"},"type":"statement","id":"Q4364558$DF210A0E-B249-4A7D-9B99-E711CFC12C15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0856aedac558dca8eb189d065081bdc67fa06a3e","datavalue":{"value":"linear congruential pseudorandom generator","type":"string"},"datatype":"string"},"type":"statement","id":"Q4364558$B7B439B1-6689-4D4C-849D-6560B1DA8E50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fadd08d3d69ec05a228d6d9c45b2bc5946a3a3b9","datavalue":{"value":"modular linear equations","type":"string"},"datatype":"string"},"type":"statement","id":"Q4364558$0AEF4669-D7A6-40BA-B868-C57CC1FFE07B","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4364558$7B779743-9C8D-4417-B28F-C935B550BAA4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6140d428e27a79dcb0a9f35319b7b90fbc26bc8","datavalue":{"value":{"entity-type":"item","numeric-id":1849602,"id":"Q1849602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"276770497f15e4b3cf766f9acbcc0e1f42347bf7","datavalue":{"value":{"amount":"+0.8453801274299622","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4364558$096CE53B-5E5C-4108-AF7F-AE9B48257541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e04e730a898087cedd6e636abfaab564c46835ca","datavalue":{"value":{"entity-type":"item","numeric-id":2870092,"id":"Q2870092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c1dc9546b3fd8012f0a9cb345874b025e13feff","datavalue":{"value":{"amount":"+0.8096378445625305","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4364558$155A4027-AC8A-47F0-98D7-9D047573B597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3668b9e03d410ce6163dff8bc3a513e96a107f6","datavalue":{"value":{"entity-type":"item","numeric-id":4035169,"id":"Q4035169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a2c483c86d735ac835bb4a170629ce53412ee7c","datavalue":{"value":{"amount":"+0.8092684745788574","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4364558$F6D9BDB4-18DB-4921-8230-32ECB09B73DB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b1d568dd02c2e27b04e76c4d534cc99b922c5501","datavalue":{"value":{"text":"`Pseudo-random' number generation within cryptographic algorithms: The DDS case","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4364558$FAB1A4E1-31D6-4C94-BF93-211A285C80A2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f8f6cc78aeb641925782c6749269a93a3fd7ee03","datavalue":{"value":"10.1007/BFB0052242","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4364558$FD4BCE84-7575-4467-A336-272C6FDC6840","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"07bfa4d47240ab3190bd069dc9857d7ab9a977df","datavalue":{"value":"It is quite well-known that popular linear congruential pseudorandom generators are not cryptographically strong in a sense that given some initial sequence produced by such generator its next bit is predictable in polynomial time. But what if such generator is used as a part of another cryptoalgorithm where output of the generator is available for internal use only and not made publicly available? The authors show that even in such settings the weak random number generators may not suffice. In other words cryptographic quality of random bits matters even when the only thing an adversary sees is the result of a one-way functions on these bits. A nice illustration of such scenario is the Digital Signature Standard (DSS) algorithm which requires the signer to generate a new ``random'' number with every signature, but an adversary (cryptanalyst) instead of the number sees only results of some calculations where the number is involved. In the article it is shown that if a linear congruential pseudorandom generator is used to produce \\textit{nonces} used by DSS then the secret key can be quickly recovered after seeing a few signatures. In other words the security of DSS relies on the secrecy of the nonces and the authors have found an attack that makes use of the weaknesses of its generator provided linear congruential pseudorandom generator is used here and its parameters except the initial seed are known. The attack described requires solving a system of simultaneous modular linear equations in different moduli. First, the \\textit{Uniqueness Lemma} is proved stating that when DSS is used with a pseudorandom number generator with high probability a few signatures are enough to uniquely determine the secret key. While the lemma holds for any pseudorandom generator, in the rest of the paper it is shown that if a linear congruential generator is used then the DSS's secret key can be quickly recovered knowing just a few signatures. This is accomplished by using a simple lattice based algorithm for solving the system of linear modular equations in different moduli. In the last part of the paper it is shown that the technique used can be generalized to include cryptanalysis of DSS where any pseudorandom generator expressible by modular linear equations is used. This is illustrated by examples of cryptanalysis of DSS using a truncated linear congruential generator and a generator that concatenates short pseudorandom numbers to obtain a long nonce. For the entire collection see [Zbl 0870.00047].","type":"string"},"datatype":"string"},"type":"statement","id":"Q4364558$C3D258C9-1FAE-4AF0-9324-D77C3A2B3D57","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4364558$6B4550B5-217F-4603-8C3E-34C977D81496","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"`Pseudo-random' number generation within cryptographic algorithms: The DDS case","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/%60Pseudo-random%27_number_generation_within_cryptographic_algorithms:_The_DDS_case"}}}}}