Shoel U'meishiv has definitely been correct in identifying Rashi as one of the earliest main sources for this Jewish legend. But since he failed to cite Rashi in full I decided to do just that (and included a translation as well) so that it is readily available to everyone. The following censored text of Rashi has already been included in the notes of all new editions of the Talmud (vagshal, oz ve'hadar), maseches Avodah Zara 10a,
Rashi explains an ambiguous text of the Talmud about Edom/Rome,
בזוי אתה מאד: שאין להן לא כתב ולא לשון
‘You are a lowly nation’ (Obadiah 1:2): That they don’t have their own
script or language.
Rashi goes on to explain the above text:
כתב ולשון: אחרים תיקנו להם כל ספרי טעותם, יוחנן, פאולוס, פיטרו'; והם
יהודים היו. לשון: הוא גראמטיקא, הוא הלטין שמדברים בו הגלחים. הם שנו
ועקמו (ש"נ עמקו) הלשון ועשן להם הבל לחשבם בפני עצמם ולסלקם מעל ישראל;
ולא שכפרו, כי לטובתן של ישראל נתכוונו; אלא מפני שראו ישראל בצער ובדוחק
מתרמיתי ישו, עשו עצמם כאלו הם עמו בקדישות, וצוו עליהם הכל כמפורש בספור
Ketav ve’Lashon: Others have given them (Christians) all their books
of folly: John, Paul, Peter; and they were all Jews. Lashon: That is
the Latin language that the bishops are fluent with. They (the
apostles mentioned before) changed their language and created folly
for them so that would become a new nation and in order to separate
them from the Jews; not because they abandoned their faith, only for
the benefit of the Jewish people did they do it; because they saw that
the Jews were in a dread and distress from the student of Jesus, so
they made themselves look as if they were with him […]  and commanded
them etc., as is recounted in the book teliyas Yeshu .
 Rashi uses a play on words and writes תרמיתי ישו (fraudsters of Jesus) instead of תלמידי ישו (students of Jesus) thereby making it clear that they were nothing more than fraudsters (תרמית).
 The Hebrew word here קדישות is ambiguous and unclear, so I did not incorporate into my translation.
 Lit. The Crucifixion of Jesus; however, it is widely accepted that this is a reference to the book Toledot Yeshu (Biography of Jesus).
It should be noted, however, that there are many reasons to doubt the authorship of this text, and I list them here:
- This Rashi is not found in any of the earlier editions or manuscripts of the Talmud. It is found only in the first edition of Ain Yaakov (Dikdukei Sofrim's only source). This should be a good enough reason to raise some doubts about its authorship and whether Rashi actually wrote it, or it is an insertion by a student from a later generation.
- It is extremely un-Rashi like to go out of his way to elaborate on the origins of Christianity; especially, in this case where it is completely unnecessary for the understanding of the Talmudic text.
- From Tosfos' question (ibid) it is clear that they were unaware of this Rashi.
These problems should raise some red flags to the serious scholar who is interested in knowing the real authorship of this text.