【源码解析】Dilithium Round3 源码解析
好久,没有开过源码阅读系列了,趁着,现在抗量子算法的热度还在,我们来看一下Dilithium提交的原码。
环境搭建
这里,我们先来看官方给出的实现,这里,我们用第三轮作者提交的实现[1]来看一下,因为最后的发布的标准,并没有给出参考实现,所以只能从之前的提交中,翻一下了。
由于,源码采用C来实现的,并且采用了OpenSSL当中的Crypto这个库,因此,如果要运行,首先需要安装这个环境,至于这个的安装办法,大家自行搜索一下吧,相信,能看到这里的,应该是会安装的,如果不安装,其实也不耽误用,其实。
接下来,其实就没太大的环境难度了,本身项目采用Makefile来构建的,直接用Clion打开就好了,坏处就是好像不好调试,目前,我也没找到好用的调试办法,然后,我又懒得转换成CMake的写法,对,就是懒,如果有好的调试Makefile方案的话,也可以和我交流。
阅读本文,需要对Dilithum的结构,有基本的认识,否则,看这个可能理解起来会比较困难,不熟悉的,可以参考下资料[1],图省事儿的,可以看下,我之前写的文章。
项目结构
这就是,下载的项目文件,具体的实现呢,在Reference_Implementation
这个文件夹下,看到了这里这么多实现,不要怕,实际上,打开那个影响都不大,每个里面,都是包含全部源码的,只不过参数开启的开关不同,这里简单介绍一下,首先是dilithium
开头的,其中包含着三个数字,2, 3, 5
,这个表示的是算法具体安全强度,具体参数,从文档[1]中看一下吧,这里,还是来简单的贴一下吧。
NIST Security Level | 2 | 3 | 5 |
---|---|---|---|
q | 8380417 | 8380417 | 8380417 |
d | 13 | 13 | 13 |
39 | 49 | 60 | |
challenge entropy | 192 | 225 | 257 |
(4, 4) | (6, 5) | (8, 7) | |
2 | 4 | 2 | |
78 | 196 | 120 | |
80 | 55 | 75 | |
Repetitions | 4.25 | 5.1 | 3.85 |
因为,每个安全等级只是参数规模不同,因此本文主要以Security Level2为基准展开讲解下。
接下来,还有一些需要说明的点,这里的随机数生成算法,之前采用的是SHAKE,用来扩展矩阵A,等其他的一些值,然后呢,后面给出了另一个实现,就是采用AES的CTR模式,来做伪随机数生成算法,因为,AES在许多硬件当中都给与了支持,没准,后面随着技术的发展,SHAKE也给内置了硬件实现了呢,好了,了解了整个项目的大致构成结构,接下来,我们就来看下具体的原码结构。
目录结构
.
├── Makefile
├── PQCgenKAT_sign.c
├── aes256ctr.c
├── aes256ctr.h
├── api.h
├── config.h
├── fips202.c
├── fips202.h
├── ntt.c
├── ntt.h
├── packing.c
├── packing.h
├── params.h
├── poly.c
├── poly.h
├── polyvec.c
├── polyvec.h
├── precomp.gp
├── randombytes.c
├── randombytes.h
├── reduce.c
├── reduce.h
├── rng.c
├── rng.h
├── rounding.c
├── rounding.h
├── sign.c
├── sign.h
├── symmetric-aes.c
├── symmetric-shake.c
├── symmetric.h
└── test
├── cpucycles.c
├── cpucycles.h
├── speed_print.c
├── speed_print.h
├── test_dilithium.c
├── test_mul.c
├── test_speed.c
└── test_vectors.c
2 directories, 39 files
可以发现,源码内容其实是不太多的,底下test
文件夹下的内容,都是一些测试样例代码以及速度测试代码,这里,就不展开讲解了,核心在上面的代码当中,PQCgenKAT_sign.c
这个,其实,也没啥用,是用来生成KAT的代码,这里,后面也不展开。我将,从api开始,然后往下来按照顺序讲解,而不是上面按照字母顺序,挨个来看。
源码概述
实现案例
这里,简单的写一个样例的代码,先运行一下,后续测试的样例代码,也都是基于这个,虽然,可能后面也用不太上。
//
// Created by littleq
//
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include "../sign.h"
#define MLEN 59
static void printArrayHex(const uint8_t m[], size_t length) {
for (size_t i = 0; i < length; i++) {
printf("%02X", m[i]);
}
}
int main(void) {
size_t mlen, smlen;
uint8_t m[MLEN] = {0};
uint8_t sm[MLEN + CRYPTO_BYTES];
uint8_t m2[MLEN + CRYPTO_BYTES];
uint8_t pk[CRYPTO_PUBLICKEYBYTES];
uint8_t sk[CRYPTO_SECRETKEYBYTES];
crypto_sign_keypair(pk, sk);
// print public key & private key
printf("public key: ");
printArrayHex(pk, CRYPTO_PUBLICKEYBYTES);
printf("n");
printf("private key: ");
printArrayHex(sk, CRYPTO_SECRETKEYBYTES);
printf("n");
crypto_sign(sm, &smlen, m, MLEN, sk);
printf("sign: ");
printArrayHex(sm, smlen);
printf("n");
int ret = crypto_sign_open(m2, &mlen, sm, smlen, pk);
if(ret) {
fprintf(stderr, "Verification failedn");
return -1;
}
return 0;
}
然后,编译也比较简单,我们照样子,写一个target就可以了。
test/test_example: test/test_example.c randombytes.c $(KECCAK_SOURCES)
$(KECCAK_HEADERS)
$(CC) $(CFLAGS) -DDILITHIUM_MODE=2
-o $@ $< randombytes.c $(KECCAK_SOURCES)
然后,运行一下,会得到如下的结果,
public key: 08054C9705F068B46768C576FCF51AA3FE08361E93306CD1043388F9DB195B0733F462655EEE9EF13A78BA78B18E202211B548EB43D1B907CC9A56A4976EABEC918ADF8F079302A92799DEAF810D76CDE7952FFEE6A9ED8DD3BD054465D83BADFB635FFD701A4BB8B06172E78DFAC4D0B4EAF4BB2F68C5062E1D1ABD6497AFC2835DA91B23EEF96BC4B02E50324F8228809077C0D8E7A86FFE369C9378B4049C1111BAF4D8B3F14B63045423383E4F63CDBAE7B17652BD604ED601C00963B3FD38B460FFE4F8A8D59A29D2AD8304D5A0D8931739F40CC6D4824CF603EB8DABDD6660B1917E2393D7ADBB48CDDC6E66E2A3C19A7C583E10E2CCD6BD3235EB3265DA0FFAD82A25D4BB4AB91963B9D82ACEC99D58A82063A6C98FF8B8C3E95DA73B882358068830841B697C8A8224830AB8650320B50317221DA75E73BF687176A09E402B9E21C9793A6B1A89271F972A2C0B16DE90BF460BC734C719FF4C500B3ED96015D63B013AE0294C207193C3581E68370763797512D21B4E15CCF96A0727A9E156EF231383113C48C199A4554049B5F66B77E8BD2CB7CBD74F5926F3C49EEF4D7D8D8A04E5A1CCF727B1D795799DEEB99C31CF0418033894674C004330DC6B35D3869202A433C1487758E31DE642E1535976A8618B19B07DF31FFE82A57E3E038532B6BDA08DB33F5A91329131DCB669094427C29B8CADDEFDCF16014CB4CD2C4FBAADFAEBA9399DC0628D9986D74722D6F5D504741610F61028C5D4F9376C78EE00C54D4CABF8D1ACC0FCD12AFA848FB90311078042692A304821FD01B00068F7BEB1FEA80678AB3765536E9E0F45B7DC5F0F92A1A7B944290DD370D23F9E9C6A3B3F8356A752A19954743F961D892EC0825B42CB9221137CBE7367A53308827BC2F97DF7443E794AD628391C98FEA8B41449F0F71B8D7E864104EA151EB0F62DF54EA418BF72DCE43E72450123D4C52751DC129DE72975DE3234F3899823E5F098B825B397AF22444D85E7406833990E9AC256DE71410D83DE4E61C8118A630A9FD082EDD9FDC9D219747B358FC0B445D288686E97180A5119D183C59CF9A4085FBABAA53B17314B9E5C0779936025C48B3C28DE4C4ABAFCDC740115E9F0AE377EA8358F7096E601B34D66C0E181C6A4565DFA9878AF835C15B4EC4FB435EE983A2883445C83CC3A1006BDE00A35885D6D0CFAB8D4C741A4ECE90383ED790755C1C1A6777BE71211EE9FA75DD72175857E27451F10812950DD1F3127716E7E14F1CE904DD0FC39037AC02BD0AA92CC8D581FBB352927828BAD2F7345374E85F618EC33201DB869DEAA1F7F67E20F0569C49C3498AB5D803903C791F41960E4D1845E612AFFD67C83CC47766AAF6434EBEAB5BA567B475E3DDC33B89204FDD46D646F413A99C6778538A7290DDF466EFB1668B337E5AF346EAB54B99C5DF1818B57A076FDBFA1EF56F69EAC9D40E8DE0AB7FD52E6E3CCED400C224444C3465B06BB23A58AC7E00CE831B75E5E82FBDE51DE3D5679CECCE33C9BDDB542E1FE6911D73F8D3CE65D1C7FC9D240F7B57077BDD86BB843EC04AB9B2440B438CF4B9B5AE619B5FE6F2718230CFAE569425BBC83FF2E766C95934CE4691B608665414E99E964E1BC8A3C0ACBB0B0770F2471E6FB2BC7170E5E8CE43A0D703AD77EF0A0CDA123C43DA8FA185F4D844FF11EABE84E9BC2968C9C0D17A89AF9F28CBA3CE86847F9C98409CABC930283EF8B00C1B53B63BFA64AB166A8A6C30051219908BAE76E2FE7180F4EA0B062EF104EFAA90DD6A7AF329C2FD3EC4A07996757AE915166A001A8DCA70AEE1F510EAFA12765629E910D560F8C834C3AB30D6329EB
private key: 08054C9705F068B46768C576FCF51AA3FE08361E93306CD1043388F9DB195B07D34E3A80A6F9454D8945F6C70790F38CB32728DCA6A6E60642E036876F0FC3B831AF358F7007B9A22773A4834DB678ED68B464E201AE6CE393AA75F4A86F8D2C1A0CE19FCAE9579C867C7994CA7962B080C8650A424DC9108A4B467259368213B94899468210240612C42960A640842885C1B22C143641C4B46019458CD304451BC60914943014A3894AA62510B1041CB3316290691395404A106918138E53426AC2348621C220DC488851C430C1360D5B184DDC00658A004124C2882300629CB4498384005A22310AC008E1088D4132084084700C312C88C63144B60D00C3240303411881911A1482DA240090A66990342891348819852DD8286D41426DC8120E811020C902710C328153460881208E431829DA04515A220E11180123150552286C2233281A4831A13281CC3251DB92680803451AA70C0833514A92241B9684A3028A0B01481B49860C458A890682CAC8855C98690A940C48C62C4A489299A47020403249228A5124868A8469190680888290C9869158A46003A800C3184162440C003751D2464C048749A0B88892322142160103070C003940523844118184238145A2807109045210B04944B48401382983166AA3226D60C08804A525229968D416410CB20180000E88362523A60884C64011232C0A366C5828441BA851504071439411810202E38841E2A004120725CA383262A05058160E1A22088416129BA2010B986D20979100072A51B48118A508D2466D8936304200061B44645B06121B0065A1A00C144050C3246602264284A04441327019C0490333080BC18062002A1430418B3645E2C68CA498451B41280992514B96804014484C1860080744E244008A02909A282521986924B48009184640464AE40081DB9821C1A080E34666039164C40065E238652131869B426CE2368D88466D91268DC8A220144732C9920513A8292233405B2471624049020869E0C041A2440C62B401203511221112C034715A864408996409078DC42409000809A2866440402D00064D5B32041A216902A830A44209E130265C942800C62821295191042A40487293A00452C611C208054CC8011A20414236402423041A032282B0654B84611A416A82C0680C046A411031620066893820CA384A4A901192C48D02C7319B02908B44010C3188C8A228484092A480215B924520C324D43444EE0218703C1338A78CBC95229DEC31F045DEDAF29516C04178D44A50CC03AE12ED0F9C45ECE23482B58848F97FA45C36C94F5FACC74CFE587462BB7C6863759C1D8ED3AFCDA5B326874043EC065B996AA5480ABB78FAB36F491E801ADD226F2017FC75684F60DA2C5CA6B37D0C21B23668EC92BACB4CD29C0DF30A89DE056BBEB938ED5A7C74F5E8E99D45E9FEFEF8CA24BE18C5995BB427B8C58AA512712C506CE7185B6410E558BF13E9694AB9CD65146B7BD23698C278FC388362D879F1274ED68F4C8BA7CB3DAE3753AC5341E830F6CA2ACA0179C5C0CFCBD6ED721C1125CFC9BAD3EB3EBB8D5EFECB632829B1A8E317430237BFDA9FBD56688E9343F347329E545C7A430AD60EB2DA43417E7A7B40E5B3C91316B704F32B9534425DA7A3D09A310AAAE413B21C5C56D49274CEB30BAB3A69503969673B8A10C3F4E283FDEC5F9DD36D4DA4A0BC555B03267D63B48AE9B922B74DA510CA49167B63F31650986B81AF855DB9A800A3DD4DE6AB4AE38CBEB78241AAAEEA31DEABC21568C033B0B0EEE4C63EB8EF69C54670A3030CFCEA16DAB8A12D050613C6FC89D9BBA6A24FEB7A42671B334F5D2C427855D809946465E5981590A4494BAC120D9D32EE9DF08FCC9C2AA525E2355BFB94A2E5BD8CACB4782677FBF0D34BB7E8EBAB7F346E7570D5807E7CB0D58B3A7083D7821F2989FAD7C11869344AAFEB24EA79460259CE01AD6E43DF5217348878132EC33447C7874B1854ADB1F1A335D44852DB89034D980337A30A08D5FF290F740C86B253AC8C65F922182C16DF8CA9F140AC5E988EE465B51805328CAE5929D92E9079B1D9753BFE0D43C66248BB85F16B7B47FAA6382F32D1772D171AFD7EE016DF088A9EC2D3CE863EFCD9A5E8F581837C33CBE91BB3BD1D7F3573E2A83F753B814331FB9C136556D776BA15CEC768FD6C14233D59F4708B486786CDF816C591545BBE7A736633215FA8EFD1FF78DEDAE2FFF9CB38AF082AC25066A738676FACDE7A202DC7FEDF8D712596515D558AEE849951C91A06F566E5EC74B0983EB431A99F2E24228EBBFCE9A9804881C404596380B6156E4EE61B83A0E4DC24417F4BA2EF3690D360B2F93C1F483575F634740DC4EBF09A4099C116B205563158540969770356246F93BD1C8B7F5EBDA7D2719FAB3B9C9D8A6BF1FC686DE5F14FDD619F5BD7CB9F607C177B7356F25DA574E200D7CD85F788874F547F1F3E4BF04F51B22EAD0B194448D4DB48705A8EF71D0E54D7777FAAEE1E942A382345740F515624D78F334ABDD9D86FE833C3134B2C05E70451097A55BCBAB8BAEEC4BF3EE50F4608BB8E427AF4D2E6AA6D509537A35EBA15FDA31698BDD64676AB5722EC6421F546427C44D4CF85E6F6B6D99FBB66E0296E53F068FCBDFFDFEDC30D54EC008A55616402CD7B1A1CD450BD491852CF4CF2FB7B899CE55528714F3F5D6A302695831DED219BB594F2BA1853BEFCE0A3A2F9B8D69C0C4EE4F466D566DF9FFE08C35E2A872D2A2F91C70C7A4D7CA1DD275D081CC35AF3139B2BBDCE88A43CC09CA3FA39A4D350EF6B1A4C6CAED60AA9E0BFFFB07EBD1E13E781771BC32B16187DFE417D76E51D01EC5EB9EE49F851291686057E4B8E21CB8BA351E06008BA6D187A53B72A153350F92A06E38EE8C79A522C189E7E454C1C9CBEF6F52FC7BD54A5636540C9774AFB7A28D3EFD4E8F89BF484F60703B0A5218DFC2AD9CF61A06901B6F0B049E616E1EDA20E3799EFEBF5BC1E3ABB8BBE79838CCDBE00BE1AE0D441699B2C2F95AD81C74BA9611EE6CE5ED4AEF58945D540F360686A0B68F8909B36978160ADD444ACE524F43015E281620E2D272B89DB37D82A2BB0EDF839C4B6D00638C60D8D0C6F208DA8E5934FD1A05C9B0C3AC544EBB01C1CC079EE774B79481C89C167B65A6726C8B76C5F49D1D734321E3EE4A2CF48E55641B8952179AB6004B664050AA89D41144FE93174577FF3B246B08F056601341F74B74CE9221E07ADFCEA03C1200F2F61ED7BE77AB85E7D54137BF135A3A46145C35FFD4B020A839FBB2460601FB746BAF2C0E027D33321D8C71727229AD23AB3FD73DD27A6C5703E10A02E3167DF4DCA25B1EEDF24FC362F7FC081309EBAB9B4E3820763F508A89DC067C3BDF02A32F821B937691E20FD3DC75CEA32794FA4DA94694A139C5CEC6D8FF64EF956555D6CF7FBEF1A6E716CA7389D77E43D1E1C6BDF36A67248808FF401E6CA6B5DFF36EEC54CD42E36721F8D3F7ECBA63C8663C2B2D985B60592C44FC630F5A44DF27D017785CB372E08936C818B4C9A39075196D18D32608A31753DBF71AB9B475956981CB935775B77C8E25ECF44
sign: 961422BC5D57EAA8B27DE3696EB5456D77B08FA3C2AA398F1D3B55F1D743DA2C41FE2C567A88D5AEEE363A6B2C905E0AB54A89206A47B01C9A0AC748569B8B9DC0562247C5F576C8C6AAB3406F1D78B46FFF719F5245BD7BC355898A29F3A5C50A7074FB3B777A718F56FDE445383D4BBE0C69C89EB5C6D876C70B6BFDD899C7D34769AEE964800F3CED7E7433C4C7F99675BF42C09CFE667D52847FFEC3D6F229FA44059955119CBBFD7CF9C025E69A852AFD1333944B4BBA58B93419C11A8157A57FB896C4A33CCE47634E999B343553C37C62975F6139FA6BFB843F17466563D97D89236E058283E394B2F889715C6E2FFD9BB9FB1FCD3572E849C70C6CCB9FF3E466B7437D6889592350CD19328B48CE2FE374F2A880C52CCB696805CA66FA6AD1CDD1E03B11DA6C5CA12011C17B2E3096D082E5E229D3B6B264471D58586DF3D8F04B0B736A950E88F6FC51C480D3A73A2051B78235FBD4BFBC56FBF727ECF799DB1D9F16F387096CAA63D7F6F2308EC96C4DA3A06B92598C54239AAE3EF44A2A8C8A9E3721486747493F04E4289BF2508BAAF8AC725584F8A1722C1E45A68948CE75D5B50075A8A4572C32B8F544CBFE319E16F07FE69A4B8C648D9400881F19AF212F2470106A3679990644B479B8D3003B09D71F7CADF53ED8F5F31603366D61F51ED57ECBAAB0739BA6A8A8EF3BD29A87ABCB3A28C779750761F200011DF87F4B42096E6E8776F8F292D9D8B7D059349A50D0D2F9E5A742E19CFD6306A4A88C71968BC37026A09EB2FF914716E860A5245D85AE26AE80A296504587A542875EB10A7F38DF90E5DA5AE45F243DD6B93545F326BC90909779C0C28DCEC16124D24AF8C208CC06BD0A12A4CFC285457D984AEF747A6BBBA61DFE59E61D7D45EC6FF1FCC3EBB48E00F493BC4A0D5D113FB7CA0973A42CF99D5B6F8C1106FB802AADED63593BD9298B446ACC5DD35DE74C2EB1AC9DD33A3126614FFF4429A89576F97C9378F3C55418ADE6775E2AD4A99C3A3D0AF65B7223F97076B5926B119AFA9AA63F0AE1C26F9E8C8AD4C808D83A35DFB4A812FB2D4B78DC3D5FB3D83CE3F161DB14BE1E77074E7545639719FF8A686B401E269CF497AC51F1D52CA35C3095A9532184869108FFDCB72F155D6EA40F794A29290A3ABBCCCC8F62F6CC32AA8D0C29BD8823446E7D4132D6EA4430A640AB4987FF8169C85CC2AB323BA723DFDE4CF906F3FC5DC775ADC2037AAFBD66E32A06573027A8191C4DF9060907C8B4D9C99ABFADD0894198B37BD64D84F6093B53F052F01A3F73C65456E27318A24FB321843516881610B8B8B37695BC17CD44105187EE2888DC8A4488BD8A210E61DA0558F19A823A85DDDB27A471A7C3797D55C0D9EC0E1F8DFA88E0AFC2BF74098C7304F1977B23FEF1F1D60B38CF71282EE58A98EE3442A6DC1A1597F2837CBD795C3DF5A18F33FBA985ED3387F685EFAA6BE93D60FD5C1C8985F3B1C44E926EB35747997D346F45F3F9A073C4D55C7C0B5680ADF64DE06D975F23FC050A5BF6FEACFD063A6A4DF541B5A750EFD7F091DC9D3DB953ED93B112B66A7FE94975F3FE5697C40A07FA7016392C0E3CE6874389144DB52E5D054D90FCFBE4A3451EAF7A4AA23568623195F7FADA2310F974517B2DCD8E2A652780D0A0EF01285884A417AD42E803DDB138BAE81DA69FDB11763F2C129F1F7D0614EFD559DD85C6A2253F7C66F192B40E3188E5217B4985E4C3C347AACA50B48F01F70CEB68C3798ED7F821D05F06E6C0A7DAE4FC853E4BF15B1BADFA71E11F3200492F0FDAA3A1D4A312F19758CBC3D6D5F9D4633DF2D752181D4D31002D8C0B9A8DD26AD326651176DEE37E7C035707AD2B503AB6464AC0B9895DEFA962487FE81982CBCF9A3DB3C4A90DE829B9A220C128A867981C6D9026EE160DAF1AD9258647E891F49D7609FD7A0D538378C3D76F25CA0D658BC01B3C255D1C40064B7F709C83CCED9A6A2FC90E3F7806C5509ED287203D4286B8B628525D2A3C694A9B4CC5285991800FE683FE4E1ED20A81D55867FE078869F0BA64729559A2D3DEDF9C9B303FC07539B2607F3D6417B0532734A133659B6494BDD7BE06B91A2E988E2481FC0D5CBA1E2AC760735F0183A57B1455BA08E157E95F0656A22E9BF059A6BA7245308DC4604350ACE8145B9D4306D13DCA638D3FE697B51B3D293F5FC20E9757302C185711A108334C6FEDFDB464976A2CE3A6BD698B46C551960468596BC2C07F69DC518A9BCCADB1B7AB08A951109006D9956F69DE3B64F3BC6B3B6026C70B3C87868098EBBF8492409274A69C82FC3CF5E3C80D847B2CB5AE0C7ADDCB395BAD44D23BA3141E3D5CDEE62BBBE54AE9CE3E5A0B1EF7AB46F8FB837353E32355A226669490DFAC3E057B59B5B0E973554317896DD84CC6F51EB4F954BBA780F00FB8799CD87D4BBEAD491A6EF062909F36FA843193FEA17241C5BDD962B9BE2BD81024C2FF7E64A7BC4E14F534BBD80AEC643F7119189D7C3BFB20DE4ACDD43C615FD9F95035DF915CB485E6CFA2C4503134751BE6FA1BE1591889559EAFD48E5F87318CA990DCC81D17F60CF242F9FDF39755879C057CD6A705C7C6E6AC9423A7947F62CF1320B4BCE34694EAF6C2AF4087AF9801382F8C5C4B8FC6E4C51BB4ABFC9B6EBDF58518A38B22279CE80FBEEDDD3D123448B7D58575A21F874B8F545A7B3DD89E56F4C3E5A0AB0144029B3E04757615C6A60918958593543A077935C666E95F7AE30522A3BC358EA6F1DB4C50587F3BC4B0794107DB4F98AA8426FDE05BF3AD6BDC84D10A6BB819D2D47562061957BD1386B15734E3486145DFB248E473185BADA0ABC677CD57DAD7B9A35FF32683050B5EA2552420AFF2A3F1F42509B4A9C0C62F55CA46F0102D4ED5D8EC1F51813DBE4829377A3EE1178154ACA9106E96BB08C4C9C6B062A0F5F56E40B58C03F3D1F7B8E1FA5FAB15F2CB236A7BEB4E68E6018A91262C08BE6D1408E420E3A91E77F1B52C718C798B3D6FAD7C271BEDE662897000692ED2F5CF228C80605C3C5604830303839F392AF497F4D26E8975CEBCB529A1CE2347FE81935C66337AAD8EBBB4A2B49A5502982E08ABBC45EA02789668757DAEB3252E5ABCCD3EC8C0DD479432AADBB157E2DFBE5749F5720F43B60ECAFD156B1DCE09793CF621BD4B702B4ACB57DD7E68058E26D965D429700099A5FA9F5093152A89081C1D55B1FDDD9C00A99A5FC0FEC1526EB6BC2B21420819DD9F1FAD4577829581449099ED573F5F8B1F0C772E3EE787286A11370B7309493B720413202C2F3A416075798B9EBAC7D2FE10174F515360626E707D858D9DAAB4B6C2D7DADDDFE0E109276365717281B7BCE00B203D44494D526B747A82ACCBCEE4E8EDF2FD000000000000000000000000102731440000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
当然,如果,你们运行,结果,大概率和我的不一样,因为里面涉及到随机的东西,好了,现在已经运行起来了,接下来呢,我们就来看一下,那么,接下来,我们先来看一下API,这里,描述了整个签名过程所用到的三个函数,实际上呢,后面,也会根据这三个函数来展开描述整个完整的代码。
API
这里,还是简单贴一下源码
#ifndef API_H
#define API_H
#include "config.h"
#if DILITHIUM_MODE == 2
#define CRYPTO_PUBLICKEYBYTES 1312
#define CRYPTO_SECRETKEYBYTES 2544
#define CRYPTO_BYTES 2420
#elif DILITHIUM_MODE == 3
#define CRYPTO_PUBLICKEYBYTES 1952
#define CRYPTO_SECRETKEYBYTES 4016
#define CRYPTO_BYTES 3293
#elif DILITHIUM_MODE == 5
#define CRYPTO_PUBLICKEYBYTES 2592
#define CRYPTO_SECRETKEYBYTES 4880
#define CRYPTO_BYTES 4595
#endif
#define crypto_sign_keypair DILITHIUM_NAMESPACE(_keypair)
int crypto_sign_keypair(unsigned char *pk, unsigned char *sk);
#define crypto_sign DILITHIUM_NAMESPACE()
int crypto_sign(unsigned char *sm, unsigned long long *smlen,
const unsigned char *msg, unsigned long long len,
const unsigned char *sk);
#define crypto_sign_open DILITHIUM_NAMESPACE(_open)
int crypto_sign_open(unsigned char *m, unsigned long long *mlen,
const unsigned char *sm, unsigned long long smlen,
const unsigned char *pk);
#endif
我们可以发现,不同的安全层级,这里的公钥和私钥长度也是在变化的,具体长度如下表[1]。
NIST Security Level | 2 | 3 | 5 |
---|---|---|---|
public key size(bytes) | 1312 | 1952 | 2592 |
signature size(bytes) | 2420 | 3293 | 4595 |
这里,里面还有一个config.h
的函数,这里,配置了具体采用的安全层级以及PRNG算法,采用SHAKE还是AES-CTR,具体和对应的文件夹相对应。
#ifndef CONFIG_H
#define CONFIG_H
#define DILITHIUM_MODE 2 // 安全等级
#define DILITHIUM_USE_AES // 是否使用AES
#define CRYPTO_ALGNAME "Dilithium2"
#define DILITHIUM_NAMESPACE(s) pqcrystals_dilithium2_ref##s
#endif
这里,先完成一个概述,然后,接下来,就来看一下代码的细节。
源码解析
这里,我们将源码的结构,分成几个部分来展开来讲,这里先不按照密钥生成、签名算法、签名验证算法来讲解,先讲解下里面用到的一些函数,后面讲起来就简单了,这里我们将函数,分成几个部分。
多项式运算
我们知道,Dilithium核心操作是基于模下的运算,而在模当中,最核心的运算也就是多项式相关的运算,这里核心的代码,都在poly.c
这个文件下。这里,就不一个函数一个函数的展开来讲解了,核心就是包含了多项式的加法、减法以及乘法运算,值得注意的一点是,对于乘法运算,这里采用了NTT进行加速。
Pack/Unpack函数
我们知道,多项式是采用数组来存储的,在上面,我们已经看了,在多项式当中的相关运算,接下来,我们就来看下,我们应该如何存储这些多项式的系数的值。我们知道,一般我们存储的格式,主要是字节,但是呢,多项式的系数,大多不在一个字节的范围之内,因此,这里,要想办法,来存储这些多项式的系数,并且,节省空间,这里,我用一个函数为例,其余的函数,原理相似,读者可以自行阅读。
/*************************************************
* Name: polyt1_pack
*
* Description: Bit-pack polynomial t1 with coefficients fitting in 10 bits.
* Input coefficients are assumed to be standard representatives.
*
* Arguments: - uint8_t *r: pointer to output byte array with at least
* POLYT1_PACKEDBYTES bytes
* - const poly *a: pointer to input polynomial
**************************************************/
void polyt1_pack(uint8_t *r, const poly *a) {
unsigned int i;
for(i = 0; i < N/4; ++i) {
r[5*i+0] = (a->coeffs[4*i+0] >> 0);
r[5*i+1] = (a->coeffs[4*i+0] >> 8) | (a->coeffs[4*i+1] << 2);
r[5*i+2] = (a->coeffs[4*i+1] >> 6) | (a->coeffs[4*i+2] << 4);
r[5*i+3] = (a->coeffs[4*i+2] >> 4) | (a->coeffs[4*i+3] << 6);
r[5*i+4] = (a->coeffs[4*i+3] >> 2);
}
}
这个Pack函数,是用来对t进行处理的,考虑到t多项式数值的范围,这里分成了10个比特一组,然后分别处理成为5个字节,最终输出在r当中(这里,我删掉了计时相关函数,这个不是我们现在所关注的)。
对于Unpack来说,只需要反向操作就好了,这里,直接贴出来代码,也不难理解,最后的0x3FF
, 恰好10个比特。
/*************************************************
* Name: polyt1_unpack
*
* Description: Unpack polynomial t1 with 10-bit coefficients.
* Output coefficients are standard representatives.
*
* Arguments: - poly *r: pointer to output polynomial
* - const uint8_t *a: byte array with bit-packed polynomial
**************************************************/
void polyt1_unpack(poly *r, const uint8_t *a) {
unsigned int i;
for(i = 0; i < N/4; ++i) {
r->coeffs[4*i+0] = ((a[5*i+0] >> 0) | ((uint32_t)a[5*i+1] << 8)) & 0x3FF;
r->coeffs[4*i+1] = ((a[5*i+1] >> 2) | ((uint32_t)a[5*i+2] << 6)) & 0x3FF;
r->coeffs[4*i+2] = ((a[5*i+2] >> 4) | ((uint32_t)a[5*i+3] << 4)) & 0x3FF;
r->coeffs[4*i+3] = ((a[5*i+3] >> 6) | ((uint32_t)a[5*i+4] << 2)) & 0x3FF;
}
}
然后,我们通过一个图,来看一下这个过程。
具体的分组长度,取决于多项式系数的范围。
支持函数
这里,不是仅仅指的在Dilithium里面提到的Supporting 算法,这里我们把比如多项式的派生算法等其他的辅助的算法,都放了进来,注意下区别,因为剩下的也不好分类,所以就都放进来了。这里就不贴源码了,里面的函数都比较好理解。
我们看完了,内部使用的一些具体的函数的分类呢,后面我们就根据顺序,来看一下三个核心的算法,密钥生成、签名以及验签算法。
密钥生成函数(crypto_sign_keypair)
int crypto_sign_keypair(unsigned char *pk, unsigned char *sk);
-
pk: 生成的公钥, 长度为 CRYPTO_PUBLICKEYBYTES
-
sk: 生成的私钥, 长度为 CRYPTO_SECRETKEYBYTES
我们,来看一下他的具体的实现的源码,这个源码呢,其实并不长,并且,注释写的也挺明了的。
/*************************************************
* Name: crypto_sign_keypair
*
* Description: Generates public and private key.
*
* Arguments: - uint8_t *pk: pointer to output public key (allocated
* array of CRYPTO_PUBLICKEYBYTES bytes)
* - uint8_t *sk: pointer to output private key (allocated
* array of CRYPTO_SECRETKEYBYTES bytes)
*
* Returns 0 (success)
**************************************************/
int crypto_sign_keypair(uint8_t *pk, uint8_t *sk) {
uint8_t seedbuf[3*SEEDBYTES];
uint8_t tr[CRHBYTES];
const uint8_t *rho, *rhoprime, *key;
polyvecl mat[K];
polyvecl s1, s1hat;
polyveck s2, t1, t0;
/* Get randomness for rho, rhoprime and key */
randombytes(seedbuf, SEEDBYTES);
shake256(seedbuf, 3*SEEDBYTES, seedbuf, SEEDBYTES);
rho = seedbuf;
rhoprime = seedbuf + SEEDBYTES;
key = seedbuf + 2*SEEDBYTES;
/* Expand matrix */
polyvec_matrix_expand(mat, rho);
/* Sample short vectors s1 and s2 */
polyvecl_uniform_eta(&s1, rhoprime, 0);
polyveck_uniform_eta(&s2, rhoprime, L);
/* Matrix-vector multiplication */
s1hat = s1;
polyvecl_ntt(&s1hat);
polyvec_matrix_pointwise_montgomery(&t1, mat, &s1hat);
polyveck_reduce(&t1);
polyveck_invntt_tomont(&t1);
/* Add error vector s2 */
polyveck_add(&t1, &t1, &s2);
/* Extract t1 and write public key */
polyveck_caddq(&t1);
polyveck_power2round(&t1, &t0, &t1);
pack_pk(pk, rho, &t1);
/* Compute CRH(rho, t1) and write secret key */
crh(tr, pk, CRYPTO_PUBLICKEYBYTES);
pack_sk(sk, rho, tr, key, &t0, &s1, &s2);
return 0;
}
算法回顾
有了前面的基础呢,我们先来回顾一下算法的过程,这里,我们捎带着描述一下对应的代码位置
-
,这里是生成一个随机的种子,也就是第22行的代码的操作 -
,这里根据之前生成的种子,通过哈希函数,来扩展出来三个新的种子,其中用作派生公钥的矩阵,用于派生私钥的多项式,用于后续的签名过程。这里具体长度都是256bits. -
计算公钥矩阵, 对应函数 polyvec_matrix_expand
, 注意这里直接生成的是NTT的表示形式 -
生成私钥向量
-
计算,这里注意计算乘法的时候用的是NTT的表示形式,计算加法的时候,采用的标准形式 -
生成公钥,其中公钥输出,对应 pack_pk
函数,注意是一个多项式,需要做一些转换 -
生成公钥,这里计算,最终拼接私钥输出
这里,实际上,我们是可以直接通过最初的种子来生成私钥的全部内容的,我猜测,存储其他的,可能是为了加速运算吧,如果想要省空间,其实可以只存最原始的种子,其他的都可以计算出来。
签名函数(crypto_sign)
这里,我们还是先来看一下,这个函数的签名
int crypto_sign(unsigned char *sm, unsigned long long *smlen,
const unsigned char *msg, unsigned long long len,
const unsigned char *sk);
-
sm: 签名输出的内容 -
smlen: 签名输出的长度,这里长度是「签名本身的长度+消息的长度」 -
msg: 原始的待签名消息 -
len: 原始的待签名消息的长度 -
sk: 私钥(这里是「打包」后的私钥)
注意,这里,的最后sm输出的内容,实际是是包含了原始消息的,然后,我们来看一下具体的实现源码。
/*************************************************
* Name: crypto_sign
*
* Description: Compute signed message.
*
* Arguments: - uint8_t *sm: pointer to output signed message (allocated
* array with CRYPTO_BYTES + mlen bytes),
* can be equal to m
* - size_t *smlen: pointer to output length of signed
* message
* - const uint8_t *m: pointer to message to be signed
* - size_t mlen: length of message
* - const uint8_t *sk: pointer to bit-packed secret key
*
* Returns 0 (success)
**************************************************/
int crypto_sign(uint8_t *sm,
size_t *smlen,
const uint8_t *m,
size_t mlen,
const uint8_t *sk)
{
size_t i;
for(i = 0; i < mlen; ++i)
sm[CRYPTO_BYTES + mlen - 1 - i] = m[mlen - 1 - i];
crypto_sign_signature(sm, smlen, sm + CRYPTO_BYTES, mlen, sk);
*smlen += mlen;
return 0;
}
看这个,其实,没什么重点,核心函数在crypto_sign_signature
, 从这里,可以看出,这里的消息是拼接在签名之后的,从我们最开始的输出,也可以得到验证,那么接下来,我们来看下crypto_sign_signature
这个函数,还是先来看下函数签名。
int crypto_sign_signature(uint8_t *sig, size_t *siglen,
const uint8_t *m, size_t mlen,
const uint8_t *sk);
这里面,就比较好理解和上面的那个函数是差不多的,只不过,这里的sig就只存储签名的内容了。
/*************************************************
* Name: crypto_sign_signature
*
* Description: Computes signature.
*
* Arguments: - uint8_t *sig: pointer to output signature (of length CRYPTO_BYTES)
* - size_t *siglen: pointer to output length of signature
* - uint8_t *m: pointer to message to be signed
* - size_t mlen: length of message
* - uint8_t *sk: pointer to bit-packed secret key
*
* Returns 0 (success)
**************************************************/
int crypto_sign_signature(uint8_t *sig,
size_t *siglen,
const uint8_t *m,
size_t mlen,
const uint8_t *sk)
{
unsigned int n;
uint8_t seedbuf[2*SEEDBYTES + 3*CRHBYTES];
uint8_t *rho, *tr, *key, *mu, *rhoprime;
uint16_t nonce = 0;
polyvecl mat[K], s1, y, z;
polyveck t0, s2, w1, w0, h;
poly cp;
keccak_state state;
rho = seedbuf;
tr = rho + SEEDBYTES;
key = tr + CRHBYTES;
mu = key + SEEDBYTES;
rhoprime = mu + CRHBYTES;
unpack_sk(rho, tr, key, &t0, &s1, &s2, sk);
/* Compute CRH(tr, msg) */
shake256_init(&state);
shake256_absorb(&state, tr, CRHBYTES);
shake256_absorb(&state, m, mlen);
shake256_finalize(&state);
shake256_squeeze(mu, CRHBYTES, &state);
#ifdef DILITHIUM_RANDOMIZED_SIGNING
randombytes(rhoprime, CRHBYTES);
#else
crh(rhoprime, key, SEEDBYTES + CRHBYTES);
#endif
/* Expand matrix and transform vectors */
polyvec_matrix_expand(mat, rho);
polyvecl_ntt(&s1);
polyveck_ntt(&s2);
polyveck_ntt(&t0);
rej:
/* Sample intermediate vector y */
polyvecl_uniform_gamma1(&y, rhoprime, nonce++);
z = y;
polyvecl_ntt(&z);
/* Matrix-vector multiplication */
polyvec_matrix_pointwise_montgomery(&w1, mat, &z);
polyveck_reduce(&w1);
polyveck_invntt_tomont(&w1);
/* Decompose w and call the random oracle */
polyveck_caddq(&w1);
polyveck_decompose(&w1, &w0, &w1);
polyveck_pack_w1(sig, &w1);
shake256_init(&state);
shake256_absorb(&state, mu, CRHBYTES);
shake256_absorb(&state, sig, K*POLYW1_PACKEDBYTES);
shake256_finalize(&state);
shake256_squeeze(sig, SEEDBYTES, &state);
poly_challenge(&cp, sig);
poly_ntt(&cp);
/* Compute z, reject if it reveals secret */
polyvecl_pointwise_poly_montgomery(&z, &cp, &s1);
polyvecl_invntt_tomont(&z);
polyvecl_add(&z, &z, &y);
polyvecl_reduce(&z);
if(polyvecl_chknorm(&z, GAMMA1 - BETA))
goto rej;
/* Check that subtracting cs2 does not change high bits of w and low bits
* do not reveal secret information */
polyveck_pointwise_poly_montgomery(&h, &cp, &s2);
polyveck_invntt_tomont(&h);
polyveck_sub(&w0, &w0, &h);
polyveck_reduce(&w0);
if(polyveck_chknorm(&w0, GAMMA2 - BETA))
goto rej;
/* Compute hints for w1 */
polyveck_pointwise_poly_montgomery(&h, &cp, &t0);
polyveck_invntt_tomont(&h);
polyveck_reduce(&h);
if(polyveck_chknorm(&h, GAMMA2))
goto rej;
polyveck_add(&w0, &w0, &h);
polyveck_caddq(&w0);
n = polyveck_make_hint(&h, &w0, &w1);
if(n > OMEGA)
goto rej;
/* Write signature */
pack_sig(sig, sig, &z, &h);
*siglen = CRYPTO_BYTES;
return 0;
}
算法回顾
我们,还是通过回顾下算法的过程,来看一下上面具体的代码。
-
还原,在此之前,需要做unpack, 来提取出来私钥的具体内容,也就是21~34行 -
然后,计算 -
计算,,这里根据资料[1]的描述,也可以随机获取,也就是 DILITHIUM_RANDOMIZED_SIGNING
这个的控制作用 -
计算,满足一定的条件,具体细节,这里不展开了 -
输出签名并且进行打包,注意代码第二个参数的sig实际上是
验签函数(crypto_sign_open)
还是老样子了,我们来看一下签名。
int crypto_sign_open(unsigned char *m, unsigned long long *mlen,
const unsigned char *sm, unsigned long long smlen,
const unsigned char *pk);
-
m: 消息内容(这是一个输出,输出原始的消息m) -
mlen: 消息长度 -
sm: 签名内容 -
smlen: 签名长度 -
pk: 签名公钥(压缩后)
这块的注释描述,我感觉有些问题,我们先来看一下,具体的实现。
/*************************************************
* Name: crypto_sign_open
*
* Description: Verify signed message.
*
* Arguments: - uint8_t *m: pointer to output message (allocated
* array with smlen bytes), can be equal to sm
* - size_t *mlen: pointer to output length of message
* - const uint8_t *sm: pointer to signed message
* - size_t smlen: length of signed message
* - const uint8_t *pk: pointer to bit-packed public key
*
* Returns 0 if signed message could be verified correctly and -1 otherwise
**************************************************/
int crypto_sign_open(uint8_t *m,
size_t *mlen,
const uint8_t *sm,
size_t smlen,
const uint8_t *pk)
{
size_t i;
if(smlen < CRYPTO_BYTES)
goto badsig;
*mlen = smlen - CRYPTO_BYTES;
if(crypto_sign_verify(sm, CRYPTO_BYTES, sm + CRYPTO_BYTES, *mlen, pk))
goto badsig;
else {
/* All good, copy msg, return 0 */
for(i = 0; i < *mlen; ++i)
m[i] = sm[CRYPTO_BYTES + i];
return 0;
}
badsig:
/* Signature verification failed */
*mlen = -1;
for(i = 0; i < smlen; ++i)
m[i] = 0;
return -1;
}
他后面说,can be equal to sm
,但是,实际上,从后面的代码可以看出,签名验证通过之后,拷贝的只是原始消息的内容,原始的签名,并没有拷贝,输出长度,也是smlen - CRYPTO_BYTES
,因此,这里最终得到的就是消息m。
好了,我们来看一下,重点的函数,也就是crypto_sign_verify
,首先,还是先来看一下,函数签名。
int crypto_sign_verify(const uint8_t *sig,
size_t siglen,
const uint8_t *m,
size_t mlen,
const uint8_t *pk);
-
sig: 签名内容(不带消息) -
siglen: 签名长度,sig的长度 -
m: 原始消息 -
mlen: 原始消息长度 -
pk: 公钥(打包后)
还是,先来贴一下原始的代码,整个逻辑还是比较清晰的。
/*************************************************
* Name: crypto_sign_verify
*
* Description: Verifies signature.
*
* Arguments: - uint8_t *m: pointer to input signature
* - size_t siglen: length of signature
* - const uint8_t *m: pointer to message
* - size_t mlen: length of message
* - const uint8_t *pk: pointer to bit-packed public key
*
* Returns 0 if signature could be verified correctly and -1 otherwise
**************************************************/
int crypto_sign_verify(const uint8_t *sig,
size_t siglen,
const uint8_t *m,
size_t mlen,
const uint8_t *pk)
{
unsigned int i;
uint8_t buf[K*POLYW1_PACKEDBYTES];
uint8_t rho[SEEDBYTES];
uint8_t mu[CRHBYTES];
uint8_t c[SEEDBYTES];
uint8_t c2[SEEDBYTES];
poly cp;
polyvecl mat[K], z;
polyveck t1, w1, h;
keccak_state state;
if(siglen != CRYPTO_BYTES)
return -1;
unpack_pk(rho, &t1, pk);
if(unpack_sig(c, &z, &h, sig))
return -1;
if(polyvecl_chknorm(&z, GAMMA1 - BETA))
return -1;
/* Compute CRH(CRH(rho, t1), msg) */
crh(mu, pk, CRYPTO_PUBLICKEYBYTES);
shake256_init(&state);
shake256_absorb(&state, mu, CRHBYTES);
shake256_absorb(&state, m, mlen);
shake256_finalize(&state);
shake256_squeeze(mu, CRHBYTES, &state);
/* Matrix-vector multiplication; compute Az - c2^dt1 */
poly_challenge(&cp, c);
polyvec_matrix_expand(mat, rho);
polyvecl_ntt(&z);
polyvec_matrix_pointwise_montgomery(&w1, mat, &z);
poly_ntt(&cp);
polyveck_shiftl(&t1);
polyveck_ntt(&t1);
polyveck_pointwise_poly_montgomery(&t1, &cp, &t1);
polyveck_sub(&w1, &w1, &t1);
polyveck_reduce(&w1);
polyveck_invntt_tomont(&w1);
/* Reconstruct w1 */
polyveck_caddq(&w1);
polyveck_use_hint(&w1, &w1, &h);
polyveck_pack_w1(buf, &w1);
/* Call random oracle and verify challenge */
shake256_init(&state);
shake256_absorb(&state, mu, CRHBYTES);
shake256_absorb(&state, buf, K*POLYW1_PACKEDBYTES);
shake256_finalize(&state);
shake256_squeeze(c2, SEEDBYTES, &state);
for(i = 0; i < SEEDBYTES; ++i)
if(c[i] != c2[i])
return -1;
return 0;
}
算法回顾
还是老样子了,通过算法来看下源码
-
还原,在此之前,需要做unpack, 来提取出来公钥的内容,也就是20~34行的内容 -
计算 -
计算 -
根据条件,判断是否验签通过,也就是最终比较c和c2的值
总结
本文,主要是针对于Dilithium所提交的第三轮的代码,进行了一下阅读,整个代码,看起来,还是相对来说比较容易理解的,前提是,能够理解dilithium本身的结构,好了,到这里,本文就结束了,又双叒叕的水了一篇文章,哈哈,有空的时候,对于其他的算法的实现,也带着大家看下吧,看心情了这个,溜了~~
参考资料
-
https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions -
https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.pdf -
https://eprint.iacr.org/2019/420.pdf
原文始发于微信公众号(Coder小Q):【源码解析】Dilithium Round3 源码解析
- 左青龙
- 微信扫一扫
- 右白虎
- 微信扫一扫
评论