В начале 20-х годов укрепление советской власти позволило правительству серьезно заняться вопросом восстановления российской криптографической службы, полностью разрушившейся после революционных событий 1917 года. Известна запись Ленина, относящаяся к 1922 году: «Сообщают об английском изобретении в области радиотелеграфии, передающем радиотелеграммы тайно. Если бы удалось купить это изобретение, то радиотелеграфная и радиотелефонная связь получили бы еще более громадное значение для военного дела».
Одновременно с работой по совершенствованию своих шифров Советский Союз начал активно заниматься прикладным криптоанализом. Наиболее ярко этот интерес советского государства к шифрсистемам других стран проявился в нелегальной работе Всероссийской чрезвычайной комиссии по борьбе с контрреволюцией и саботажем (ВЧК), созданной в 1918 году. В ее функции изначально вошел контроль за иностранной перепиской. Уже в первой половине 20-х годов в Москве находились посольства и торговые миссии Англии, Афганистана, Германии, Ирана, Италии, Польши, Турции и прибалтийских государств. Копии шифртелеграмм, которые сотрудники этих посольств и миссий отправляли с московского телеграфа, неизменно доставлялись в ВЧК. Часть дипломатической шифрпереписки, а также шифрованных радиограмм Белой армии перехватывалась на подмосковной военной радиостанции и на Шаболовской радиостанции в Москве.
Перехваченные шифрсообщения направлялись в ВЧК, где предпринимались попытки их дешифровать. Там 5 мая 1921 г. постановлением советского правительства была создана криптографическая служба — Специальный отдел. Ввиду особого значения Спецотдела, а также в связи с тем, что его начальник имел очень большое влияние в партийных верхах, это подразделение фактически не подчинялось руководству органов госбезопасности, а находилось в ведении партии. В результате, несмотря на все многочисленные довоенные реорганизации этих органов, Спецотдел всегда оставался вне ведомственных рамок, то есть пользовался автономией. Сотрудники других чекистских подразделений относились к Спецотделу скептически, так как «там никого не арестовывали и не допрашивали».
В связи с организацией Спецотдела 25 августа 1921 г. в ВЧК был издан приказ, который предписывал всем подразделениям в центре и на местах всякого рода шифры, ключи к ним и шифровки, обнаруженные при обысках и арестах, а также добытые через агентуру или случайно, направлять в Спецотдел.
Работа Спецотдела началась с детального изучения архивов дешифровальных служб дореволюционной России, в которых сохранились шифры вместе с подробными руководствами по их использованию, описания методов дешифрования и материалы перехвата. Среди архивных документов были, в частности, копии и подлинники шифров Болгарии, Германии, Китая, США и Японии, отчеты о работе по их вскрытию, различные учебные пособия. Сотрудники Спецотдела тщательно изучали эти материалы, сознавая всю важность такой работы. Большую роль в этот период сыграли знания и опыт криптографов со стажем. С их активным участием при Спецотделе были организованы полугодичные курсы, на которых изучались основы криптографии, решались учебные задачи по дешифрованию. На курсы набирали людей способных и образованных. Первый выпуск курсов состоял из 14 человек, почти половина из которых пришла на работу в дешифровальную секцию Спецотдела, остальные пополнили собой другие его подразделения.
К трудностям первых лет функционирования Спецотдела, связанным с относительно невысокой общей подготовленностью его сотрудников и малочисленностью личного состава, прибавились сложности, вызванные недостатком и низким качеством материалов для дешифрования. Несовершенство радиоприемной аппаратуры, ее нехватка и сильная изношенность не могли обеспечить высокой достоверности текста перехватываемых шифровок. Перед руководством Спецотдела встала задача организации и налаживания работы всех звеньев дешифровальной службы, включая добычу шифрматериалов и техническое оснащение станций перехвата.
Несмотря на испытываемые трудности, с первых месяцев своего существования Спецотдел начал успешно проводить работу по вскрытию иностранных шифров. Первый успех был достигнут при «разработке» немецкого дипломатического кода, которым пользовался полномочный представитель германского правительства в Москве. Начиная с июня 1921 года вся шифрпереписка на линии связи Москва — Берлин дешифровалась в Спецотделе. В августе того же года было осуществлено дешифрование турецких дипломатических телеграмм. Практические результаты по вскрытию польских шифров были достигнуты в 1924 году, через три года началось чтение японской шифрпереписки, а еще через три — американской.
В конце 20-х годов сотрудники Спецотдела приняли активное участие в организации дешифровальной работы в Красной Армии. Итогом этих усилий стало создание в начале 30-х годов объединенного подразделения радиоразведки ОГПУ и 4-го управления Генштаба Красной Армии в рамках Спецотдела.